Sort

贪心是一种思想，使用贪心思想解决的问题，如果能被总结成具体某一类问题，那么就有具体的名字，比如单源最短路问题，最小生成树问题，拓扑排序问题，如果不能被总结出来，那它就叫贪心问题哈哈。

贪心问题经常需要借助排序来实现。

快速排序

1. 取一个随机值作为下标，与最后一个位置交换
2. small始终指向最后一个小于pivot的下标，初始为start - 1
3. 从start开始遍历，不需要遍历最后一个数(特殊处理)
4. 当nums[i] < nums[end]，将small前移，并且交换i与small
5. 退出循环后，将small前移，与最后一个位置的数(pivot)交换

代码

package sort;

import java.util.Random;

public class test {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end) {
        if (start < end) { // 递归到子数组只有一个数字为止
            int pivot = partition(nums, start, end);
            quickSort(nums, start, pivot - 1);
            quickSort(nums, pivot + 1, end);
        }
    }

    private int partition(int[] nums, int start, int end) {
        int random = new Random().nextInt(end - start + 1) + start; // nextInt左闭右开
        swap(nums, random, end);
        int small = start - 1;
        for (int i = start; i < end; ++i)  // end存放的是pivot，退出循环特殊处理
            if (nums[i] < nums[end])
                swap(nums, ++small, i);
        swap(nums, end, ++small);
        return small;
    }

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

    public static void main(String[] args) {
        test t = new test();
        int[] arr = new int[]{3,5,8,10,34,1,544,-13};
        t.sortArray(arr);
        for (int x : arr)
            System.out.print(x + " ");
    }

}

计数排序

计数排序是一种线性时间的整数排序算法。如果数组的长度为n，整数范围(数组中最大整数与最小整数的差值)为k对于k远小于n的场景(如对某公司所有员工的年龄排序)，那么计数排序的时间复杂度优于其他基于比较的排序算法(如归并排序、快速排序)，

三次遍历！

1. 遍历原始数组nums，得出最大值max与最小值min，并创建大小为max - min + 1的count数组
2. 遍历nums数组，把对应整数num出现的次数记录在count数组的count[num - min]中
3. 令num从min遍历到max，将num顺序填入nums中(每个num有count[num - min]个)

代码

public int[] sortArray(int[] nums) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int[] count = new int[max - min + 1];
    for (int num : nums)
        ++count[num - min];
    int i = 0;
    for (int num = min; num <= max; ++num)
        while (count[num - min]-- > 0)
            nums[i++] = num;
    return nums;
}

剑指 Offer II 074. 合并区间

方法一：射气球的思路

1. 首先将数组按照左边界升序排序

2. 当intervals[i][1] >= intervals[j][0]，那么这两个元素一定是要合并的，因为是intervals数组是按照左边界升序排序的，那么合并区间[a, b]的a一定是intervals[i][0]，将intervals[i][1]赋值为intervals[i][1]与intervals[j][1]的最大值

3. 当intervals[i][1] < intervals[j][0]，那么这个两个区间是不重合的，先把上一个重合区间加入结果集，再把j赋值给i，进行下一轮循环

4. 当j == intervals.length - 1时候，

   1. 如果intervals[i][1] >= intervals[j][0]，那么会将intervals[i][1]取intervals[i][1]与intervals[j][1]的最大值
   2. 如果intervals[i][1] < intervals[j][0]，那么会将之前的重合区间存入结果集，并将j赋值给i

   所以出循环，只需要把intervals[i]加入结果集就好！

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        List<int[]> list = new LinkedList<>();
        int i = 0;
        for (int j = 1; j < intervals.length; ++j) {
            if (intervals[i][1] >= intervals[j][0])
                intervals[i][1] = Math.max(intervals[i][1], intervals[j][1]);
            else {
                list.add(new int[]{intervals[i][0], intervals[i][1]});
                i = j;
            }
        }
        list.add(new int[]{intervals[i][0], intervals[i][1]});
        return list.toArray(new int[list.size()][]);
    }
}

剑指 Offer II 075. 数组相对排序

1. 数据范围是[0, 1000]，创建大小为1001的count数组
2. 统计arr1中出现整数的个数
3. 按照arr2整数出现的顺序填arr1数组
4. 从0到1000(升序)，把剩下的数组填入arr1数组

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int num : arr1)
            ++count[num];
        int i = 0;
        for (int num : arr2) 
            while (count[num]-- > 0)
                arr1[i++] = num;
        for (int num = 0; num <= 1000; ++num) 
            while (count[num]-- > 0)
                arr1[i++] = num;
        return arr1;
    }
}

剑指 Offer II 076. 数组中的第 k 大的数字

快排找到下标为n-k的数x，左边的数都小于x，右边的数都大于x

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length, target = n - k, start = 0, end = n - 1;
        int pivot = partition(nums, start, end);
        while (pivot != target) {
            if (pivot > target)
                end = pivot - 1;
            else
                start = pivot + 1;
            pivot = partition(nums, start, end);
        }
        return nums[pivot];
    }

    private int partition(int[] nums, int start, int end) {
        int random = new Random().nextInt(end - start + 1) + start;
        swap(nums, random, end);
        int small = start - 1;
        for (int i = start; i < end; ++i) 
            if (nums[i] < nums[end])
                swap(nums, ++small, i);
        swap(nums, ++small, end);
        return small;        
    }

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