排序

使数组唯一的最小增量

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:
输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2:
输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

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

解法
1）使每个数都不一样，很自然想到排序（涉及数的大小）；排序之后，通过遍历保证每个数大于前面的一个数即可；
2）瓶颈在排序，所以考虑线性复杂度的排序；因为这里有条件每个数的都为正数，且小于40000，可以考虑使用计数排序。
算法复杂度为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];
            }
        }

        // 计数数组
        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;
            }
        }
    }

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

排序
按照区间的左边界排序后，遍历一次即可；

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

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

        // 按照第一位数排序
        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]);
    }

数组中的第K个最大元素(https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

堆

 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中的优先队列数据结构：

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 个最大元素也就是第 N - k + 1个最小元素，因此可以用第 k 小算法来解决本问题（这里下标从1开始）。

假设枢纽元的下标pivot_index，枢纽元左边的数字都小于枢纽元，右边的数字都大于枢纽元，所以pivot_index表示枢纽元是第pivot_index+1个最小的数字。每次利用枢纽元划分一次，比较（sth = N - k + 1）与 （pivot_index+1）的大小：
1）若sth小于枢纽元位置，则对枢纽元左边的元素进行递归；
2）若sth大于枢纽元位置，则对枢纽元右边的元素进行递归；
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]; // 使用下面的随机元素作为枢纽元更加快速
        // 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 个高频元素

技巧总结：
1）类似前k个最大元素，前k个最小元素的问题，可以使用堆（优先队列）接口；
2）前k大 用小根堆（前k小 用大根堆），维护堆大小不超过 k 即可，一旦超过k，出堆最小元素即可；
3）jdk的优先队列可以接受compator对象作为构造器参数，这样内部在比较元素的时候即调用compator对象；即PriorityQueue内部的涉及比较的操作实现有两套，一套是当compator变量不为null时，使用此对象进行比较；一套是当compator变量为null时，使用元素的compareTo方法；
堆（优先队列）

 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);
        }
        // 构建最小堆
        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个元素:必然是堆中最大的元素
        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;
    }

自己实现的简单的优先队列结构：这里没有实现接收compator对象的构造器；其实实现也很简单，添加compator成员变量，在比较元素大小时，使用compator.compare方法即可。这里为了代码的简洁，就不实现两套比较逻辑了。

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();
    }

    // 构建最小堆
    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, 不然仍然会执行一次 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(){
        // 末尾元素移动至堆顶,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];
        }
    }

最大数

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();
    }

    // 关键就是这个比较方法
    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();
    }

排序数组

 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;
    }

计数排序
考虑到有条件-50000<num<50000，可以利用计数排序。

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;
    }

会议室 II

    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        // 按照开始时间排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 优先队列, 按照结束时间构建最小堆
        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();
    }