使數(shù)組唯一的最小增量

給定整數(shù)數(shù)組 A，每次 move 操作將會(huì)選擇任意 A[i]，并將其遞增 1。
返回使 A 中的每個(gè)值都是唯一的最少操作次數(shù)。

示例 1:
輸入：[1,2,2]
輸出：1
解釋：經(jīng)過一次 move 操作，數(shù)組將變?yōu)?[1, 2, 3]。

示例 2:
輸入：[3,2,1,2,1,7]
輸出：6
解釋：經(jīng)過 6 次 move 操作，數(shù)組將變?yōu)?[3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能讓數(shù)組的每個(gè)值唯一的。

提示：0 <= A.length <= 40000；0 <= A[i] < 40000

解法
1）使每個(gè)數(shù)都不一樣，很自然想到排序（涉及數(shù)的大小）；排序之后，通過遍歷保證每個(gè)數(shù)大于前面的一個(gè)數(shù)即可；
2）瓶頸在排序，所以考慮線性復(fù)雜度的排序；因?yàn)檫@里有條件每個(gè)數(shù)的都為正數(shù)，且小于40000，可以考慮使用計(jì)數(shù)排序。
算法復(fù)雜度為O(N)

public int minIncrementForUnique(int[] A) {
       int count = 0;
        countSort(A);

        for (int i = 1; i < A.length; i++) {
            if (A[i] <= A[i - 1]) {
                int d = A[i-1] - A[i];
                A[i] += d+1;
                count += d+1;
            }
        }

        return count;
    }

    public static void countSort(int[] nums) {

        if(nums.length <= 1){
            return;
        }

        // 取最大值
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        // 計(jì)數(shù)數(shù)組
        int[] count = new int[max + 1];
        for (int num : nums) {
            count[num]++;
        }

        // 排序
        int ind = 0;
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                nums[ind++] = i;
            }
        }
    }

合并區(qū)間

給出一個(gè)區(qū)間的集合，請(qǐng)合并所有重疊的區(qū)間。

示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

排序
按照區(qū)間的左邊界排序后，遍歷一次即可；

    public static int[][] merge(int[][] intervals) {

        if(intervals.length <= 1){
            return intervals;
        }

        // 按照第一位數(shù)排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> merged = new ArrayList<>();
        int L = intervals[0][0];
        int R = intervals[0][1];
        for(int i=1; i<intervals.length; i++){
            if(intervals[i][0] > R){
                merged.add(new int[]{L,R});
                L = intervals[i][0];
                R = intervals[i][1];
            }else {
                R = Math.max(R, intervals[i][1]);
            }
        }
        merged.add(new int[]{L,R});

        return merged.toArray(new int[merged.size()][2]);
    }

數(shù)組中的第K個(gè)最大元素(https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。

堆

 public static int findKthLargest(int[] nums, int k) {
        buildHeap(nums);
        int len = nums.length-1;
        for(int i=0; i<k; i++){
            if(i == k-1){
                return nums[0];
            }
            swapRef(nums, 0, len--);
            percDown(nums, len, 0);
        }
        return 0;
    }

    public static void buildHeap(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            percDown(nums, nums.length, i);
        }
    }

    public static void percDown(int[] nums, int len, int k) {
        while (2 * k + 1 < len) {
            int maxChild = 2 * k + 1;
            if (maxChild + 1 < len && nums[maxChild + 1] > nums[maxChild]) {
                maxChild = maxChild + 1;
            }
            if(nums[k] < nums[maxChild]){
                swapRef(nums, k, maxChild);
            }
            k = maxChild;
        }
    }

    public static void swapRef(int[] nums, int ind1, int ind2){
        int temp = nums[ind1];
        nums[ind1] = nums[ind2];
        nums[ind2] = temp;
    }

直接利用jdk中的優(yōu)先隊(duì)列數(shù)據(jù)結(jié)構(gòu)：

public static int findKthLargest(int[] nums, int k) {
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        };
        PriorityQueue<Integer> heap = new PriorityQueue<>(comparator);
        for(int num : nums){
            heap.add(num);
        }
        for(int i=0; i<k; i++){
            int num = heap.poll();
            if(i == k-1){
                return num;
            }
        }
        return 0;
    }

快速選擇法
本方法大致上與快速排序相同。簡便起見，注意到第 k 個(gè)最大元素也就是第 N - k + 1個(gè)最小元素，因此可以用第 k 小算法來解決本問題（這里下標(biāo)從1開始）。

假設(shè)樞紐元的下標(biāo)pivot_index，樞紐元左邊的數(shù)字都小于樞紐元，右邊的數(shù)字都大于樞紐元，所以pivot_index表示樞紐元是第pivot_index+1個(gè)最小的數(shù)字。每次利用樞紐元?jiǎng)澐忠淮?，比較（sth = N - k + 1）與 （pivot_index+1）的大?。?br> 1）若sth小于樞紐元位置，則對(duì)樞紐元左邊的元素進(jìn)行遞歸；
2）若sth大于樞紐元位置，則對(duì)樞紐元右邊的元素進(jìn)行遞歸；
3）若相等，則返回樞紐元；
這相比快速排序，只需要遞歸一半即可；

 public static int findKthLargest(int[] nums, int k) {
        return recursion(nums, 0, nums.length - 1, nums.length - k + 1);
    }

    public static int recursion(int[] nums, int L, int R, int sth) {
        if (L == R) {
            return nums[L];
        }

        int pivot = nums[R]; // 使用下面的隨機(jī)元素作為樞紐元更加快速
        // Random random_num = new Random();
        // int pivot_index = L + random_num.nextInt(R - L);
        // int pivot = nums[pivot_index];
        // swapRef(nums, pivot_index, R);

        int left = L;
        int right = R;
        while (left < right) {
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            while (right > left && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {
                swapRef(nums, left, right);
            }else {
                swapRef(nums, left, R);
            }
        }

        // L -- left -- R
        if (sth == left + 1) {
            return nums[left];
        } else if (sth < left + 1) {
            return recursion(nums, L, left - 1, sth);
        } else {
            return recursion(nums, left + 1, R, sth);
        }
    }


    public static void swapRef(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

前 K 個(gè)高頻元素

技巧總結(jié)：
1）類似前k個(gè)最大元素，前k個(gè)最小元素的問題，可以使用堆（優(yōu)先隊(duì)列）接口；
2）前k大 用小根堆（前k小 用大根堆），維護(hù)堆大小不超過 k 即可，一旦超過k，出堆最小元素即可；
3）jdk的優(yōu)先隊(duì)列可以接受compator對(duì)象作為構(gòu)造器參數(shù)，這樣內(nèi)部在比較元素的時(shí)候即調(diào)用compator對(duì)象；即PriorityQueue內(nèi)部的涉及比較的操作實(shí)現(xiàn)有兩套，一套是當(dāng)compator變量不為null時(shí)，使用此對(duì)象進(jìn)行比較；一套是當(dāng)compator變量為null時(shí)，使用元素的compareTo方法；
堆（優(yōu)先隊(duì)列）

 public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numCountMap = new HashMap<>();
        for(int num :nums){
            numCountMap.put(num, numCountMap.getOrDefault(num, 0) + 1);
        }
        // 構(gòu)建最小堆
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return numCountMap.get(o1) - numCountMap.get(o2);
            }
        };
        PriorityQueue<Integer> heap = new PriorityQueue<>(comparator);
        // 只保留k個(gè)元素:必然是堆中最大的元素
        for(int num : numCountMap.keySet()){
            heap.add(num);
            if(heap.size() > k){
                heap.poll();
            }
        }
        // 返回元素
        int[] ret = new int[heap.size()];
        int ind = 0;
        while (!heap.isEmpty()){
            ret[ind++] = heap.poll();
        }
        return ret;
    }

自己實(shí)現(xiàn)的簡單的優(yōu)先隊(duì)列結(jié)構(gòu)：這里沒有實(shí)現(xiàn)接收compator對(duì)象的構(gòu)造器；其實(shí)實(shí)現(xiàn)也很簡單，添加compator成員變量，在比較元素大小時(shí)，使用compator.compare方法即可。這里為了代碼的簡潔，就不實(shí)現(xiàn)兩套比較邏輯了。

public class MyHeap<AnyType extends Comparable<? super AnyType>> {

    private AnyType[] array;
    private int currentSize;

    public MyHeap(){
        array = (AnyType[]) new Comparable[10];
    }

    public MyHeap(int size) {
        currentSize = 0;
        array = (AnyType[]) new Comparable[size];
    }

    public MyHeap(AnyType[] items) {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[currentSize * 2];
        int i = 1;
        for (AnyType item : items) {
            array[i++] = item;
        }
        buildHeap();
    }

    // 構(gòu)建最小堆
    public void buildHeap() {
        for (int i = currentSize / 2; i <= currentSize; i++) {
            percDown(i);
        }
    }

    public void percDown(int hole) {
        AnyType temp = array[hole];
        int child;
        for(; hole * 2 <= currentSize; hole = child){
            // 獲取兒子中較小者
            child = 2 * hole;
            if (array[child + 1].compareTo(array[child]) < 0) {
                child = child + 1;
            }

            // 比較大小
            if(temp.compareTo(array[child]) > 0){
                array[hole] = array[child];
            }else {
                break; // 一定要break, 不然仍然會(huì)執(zhí)行一次 hole=child
            }
        }
        array[hole] = temp;
    }

    public void add(AnyType item){
        if(currentSize >= array.length-1){
            enlarge(array.length * 2);
        }
        int hole = ++currentSize;
        for(int parent = hole / 2; parent >= 1; parent = parent / 2){
            if(array[parent].compareTo(item) > 0){
                array[hole] = array[parent];
                hole = parent;
            }else {
                break;
            }
        }
        array[hole] = item;
    }

    // 移除堆頂最小元素
    public AnyType pop(){
        // 末尾元素移動(dòng)至堆頂,currentSize大小減1
        AnyType min = array[1];
        array[1] = array[currentSize];
        array[currentSize--] = null;

        // 堆頂元素下濾
        percDown(1);
        return min;
    }

    public void enlarge(int size){
        AnyType[] old = array;
        array = (AnyType[]) new Comparable[size];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }

最大數(shù)

public static String largestNumber(int[] nums) {
        if(nums.length == 1){
            return String.valueOf(nums[0]);
        }
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        int start = 0;
        while (start < nums.length - 1 && nums[start] == 0) {
            start++;
        }
        for (int i = start; i < nums.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    // 關(guān)鍵就是這個(gè)比較方法
    public static int compare(int a, int b) {
        String ab = String.valueOf(a) + String.valueOf(b);
        String ba = String.valueOf(b) + String.valueOf(a);
        return ab.compareTo(ba);
    }

    public static void mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left == right) {
            return;
        }
        int med = (left + right) / 2;
        mergeSort(nums, temp, left, med);
        mergeSort(nums, temp, med + 1, right);
        merge(nums, temp, left, med, right);
    }

    public static void merge(int[] nums, int[] temp, int left, int med, int right) {
        int index = left;
        int ptr1 = left;
        int ptr2 = med + 1;
        while (ptr1 <= med && ptr2 <= right) {
            if (compare(nums[ptr1], nums[ptr2]) > 0) {
                temp[index++] = nums[ptr1++];
            } else {
                temp[index++] = nums[ptr2++];
            }
        }
        while (ptr1 <= med) {
            temp[index++] = nums[ptr1++];
        }
        while (ptr2 <= right) {
            temp[index++] = nums[ptr2++];
        }

        for (int i = left; i <= right; i++) {
            nums[i] = temp[i];
        }
    }

直接使用Arrays.sort方法比較：

    public static String largestNumber(int[] nums) {
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        String[] numArr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numArr[i] = String.valueOf(nums[i]);
        }
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                int result = s1.compareTo(s2);
                if (result > 0) {
                    return -1;
                } else if (result == 0) {
                    return 0;
                } else {
                    return 1;
                }
            }
        };

        Arrays.sort(numArr, comparator);

        StringBuilder sb = new StringBuilder();
        int start = 0;
        while (start < numArr.length - 1 && numArr[start].equalsIgnoreCase("0")) {
            start++;
        }
        for (int i = start; i < numArr.length; i++) {
            sb.append(numArr[i]);
        }
        return sb.toString();
    }

排序數(shù)組

 public int[] sortArray(int[] nums) {
        mergeSort(nums, new int[nums.length], 0, nums.length-1);
        return nums;
    }

    public void mergeSort(int[] nums, int[] temp, int left, int right){
        if(left >= right){
            return;
        }
        int med = (left + right) / 2;
        mergeSort(nums, temp, left, med);
        mergeSort(nums, temp, med + 1, right);
        merge(nums, temp, left, med, right);
    }

    public void merge(int[] nums, int[] temp, int left, int med, int right){
        int index1 = left;
        int index2 = med + 1;
        int tempIndex = left;
        while (index1 <= med && index2 <= right){
            if(nums[index1] < nums[index2]){
                temp[tempIndex++] = nums[index1++];
            }else {
                temp[tempIndex++] = nums[index2++];
            }
        }
        while (index1 <= med){
            temp[tempIndex++] = nums[index1++];
        }
        while (index2 <= right){
            temp[tempIndex++] = nums[index2++];
        }
        for(int i = left; i <= right; i++){
            nums[i] = temp[i];
        }
    }

快排

public void quickSort(int[] nums, int start, int end){
        if(start >= end){
            return;
        }
        int pivot = end;
        int left = start;
        int right = end;
        while (left < right){
            while (left < right && nums[left] <= nums[pivot]){
                left++;
            }
            while (left < right && nums[right] >= nums[pivot]){
                right--;
            }
            if(left < right){
                swap(nums, left, right);
            }
        }
        // 交換樞紐元和left的位置
        swap(nums, left, end);
        quickSort(nums, start, left - 1);
        quickSort(nums, left + 1, end);
    }

    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

計(jì)數(shù)排序
考慮到有條件-50000<num<50000，可以利用計(jì)數(shù)排序。

public int[] sortArray(int[] nums) {
        int max = 100001;
        int offset = 50000;
        int[] count = new int[max];
        for(int num : nums){
            count[num + offset] ++;
        }
        int index = 0;
        for(int i=0; i<max; i++){
            while (count[i] > 0){
                nums[index++] = i - offset;
                count[i] --;
            }
        }
        return nums;
    }

會(huì)議室 II

    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        // 按照開始時(shí)間排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 優(yōu)先隊(duì)列, 按照結(jié)束時(shí)間構(gòu)建最小堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        priorityQueue.add(intervals[0][1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= priorityQueue.peek()) {
                priorityQueue.poll();
            }
            priorityQueue.add(intervals[i][1]);
        }
        return priorityQueue.size();
    }