IVN
0%

MergeSort&&QuickSort

Posted on Edited on In
Symbols count in article: 13k Reading time ≈ 12 mins.

Merge Sort

  • 归并排序本质上是，先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。
  • 类似二叉树后序遍历
  • 需要辅助数组temp
  • 从整体上看，二叉树的高度是 logN，其中每一层的元素个数就是原数组的长度 N，所以总的时间复杂度就是 O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Merge {

    // 用于辅助合并有序数组
    private static int[] temp;

    public static void sort(int[] nums) {
        // 先给辅助数组开辟内存空间
        temp = new int[nums.length];
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }

    // 定义：将子数组 nums[lo..hi] 进行排序
    private static void sort(int[] nums, int lo, int hi) {
        if (lo == hi) {
            // 单个元素不用排序
            return;
        }
        // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
        int mid = lo + (hi - lo) / 2;
        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, lo, mid);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, hi);
        // 将两部分有序数组合并成一个有序数组
        merge(nums, lo, mid, hi);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int lo, int mid, int hi) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        // 数组双指针技巧，合并两个有序数组
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                // 右半边数组已全部被合并
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }
}

912. Sort an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class LeetCode912 {
    int[] temp;
    public int[] sortArray(int[] nums) {
        temp=new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    
    void mergeSort(int[] nums, int start, int end){
        if(start>=end){
            return;
        }
        int mid=start+(end-start)/2;
        mergeSort(nums,start,mid);
        mergeSort(nums,mid+1,end);
        merge(nums,start,mid,end);
    }

    void merge(int[] nums, int start, int mid, int end){
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        for(int i=start; i<=end; i++){
            temp[i]=nums[i];
        }

        int p=start;
        int i=start;
        int j=mid+1;
        while(i<=mid && j<=end){
            if(temp[i]<=temp[j]){
                nums[p++]=temp[i++];
            }else{
                nums[p++]=temp[j++];
            }
        }
        while(i<=mid){
            nums[p++]=temp[i++];
        }
        while(j<=end){
            nums[p++]=temp[j++];
        }
    }
}

315. Count of Smaller Numbers After Self

这题和归并排序什么关系呢，主要在 merge 函数，我们在使用 merge 函数合并两个有序数组的时候，其实是可以知道一个元素 nums[i] 后边有多少个元素比 nums[i] 小的。

求解「逆序对」的思想：当其中一个数字放进最终归并以后的有序数组中的时候，这个数字与之前看过的数字个数（或者是未看过的数字个数）可以直接统计出来，而不必一个一个数。这样排序完成以后，原数组的逆序数也就计算出来了；

因为在排序过程中，每个元素的索引位置会不断改变，所以我们用一个 Pair 类封装每个元素及其在原始数组 nums 中的索引，以便 count 数组记录每个元素之后小于它的元素个数。

在对 nuns[lo..hi] 合并的过程中，每当执行 nums[p] = temp[i] 时，就可以确定 temp[i] 这个元素后面比它小的元素个数为 j - mid - 1，其中i为前半部分的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class LeetCode315 {

    class Pair{ 
        int id;
        int val;
        Pair(int id,int val){
            this.id=id;
            this.val=val;
        }
    }

    Pair[] pairs; //索引数组，便于定位某一元素在初始数组中的index，用于更新结果
    Pair[] temp; //辅助索引数组，存储merge前已经排序好的前后两部分，用于merge，使merge后pairs里就是最终结果
    int[] counts;
    public List<Integer> countSmaller(int[] nums) {
        pairs=new Pair[nums.length];
        temp=new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            pairs[i]=new Pair(i,nums[i]);
        }
        counts=new int[pairs.length];
        mergeSort(pairs,0,pairs.length-1);
        List<Integer> res=new ArrayList<>();
        for (int count : counts) {
            res.add(count);
        }
        return res;
    }

    void mergeSort(Pair[] pairs, int left, int right){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        mergeSort(pairs,left,mid);
        mergeSort(pairs,mid+1,right);
        merge(pairs,left,mid,right);
    }

    void merge(Pair[] pairs, int left, int mid, int right){
        for (int i = left; i <=right; i++) {
            temp[i]=pairs[i];
        }

        int i=left;
        int j=mid+1;
        //基本逻辑同mergeSort
        //每当出现选中pairs[i]时，更新counts数组
        for(int p=left; p<=right; p++){
            if(i>mid){
                pairs[p]=temp[j++];
            }else if(j>right){
                pairs[p]=temp[i++];
                counts[pairs[p].id]+=j-mid-1;
            }else if(temp[i].val>temp[j].val){ //相等时i在前。保证pairs[i].val>pairs[j-1].val
                pairs[p]=temp[j++];
            }else{//一旦出现i.val<=j.val,就可以保证[mid+1,j)区间全部小于i.val
                pairs[p]=temp[i++];
                counts[pairs[p].id]+=j-mid-1;
            }
        }
    }
}

327. Count of Range Sum

The problem is similiar to 315. Count of Smaller Numbers After Self, yoc can click here to check how to slolve it.
The difference between two probles is that you need compute the prefix sums, cumsum[i] means nums[:i]’s prefix sums :

nums = [1,3,4]
cumsum = [0,1,4,8]
cumcum[1] means nums[:1]’s prefix sums

We just need to count those where cumsum[j] - cumsum[i] is in [lower,upper].

493. Reverse Pairs

树状数组？不必

https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int reversePairs(int[] nums) {
    return reverse(nums,0,nums.length-1);
}

int reverse(int[] nums, int l, int r){
    if(l>=r){
        return 0;
    }
    int mid=(l+r)>>1;
    int res=reverse(nums,l,mid)+reverse(nums,mid+1,r);
    int[] temp=new int[r-l+1];
    int i=l;
    int j=mid+1;
    int p=mid+1;
    int k=0;
    while(i<=mid){
        while(p<=r && nums[i]>2L*nums[p]){
            p++;
        }
        //[mid+1,p-1]
        res+=p-mid-1;
        while(j<=r && nums[i]>=nums[j]){
            temp[k++]=nums[j++];
        }
        temp[k++]=nums[i++];
    }
    while(j<=r){
        temp[k++]=nums[j++];
    }
    System.arraycopy(temp,0,nums,l,temp.length);
    return res;
}

Quick Sort

快速排序的核心无疑是 partition 函数， partition 函数的作用是在 nums[lo..hi] 中寻找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]：

912. Sort an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    int[] nums;
    int n;
    public int[] sortArray(int[] nums) {
        this.nums=nums;
        this.n=nums.length;
        sort(0,n-1);
        return this.nums;
    }

    void sort(int start, int end){
        if(start>=end){
            return;
        }
        int j=partition(start,end);
        sort(start,j-1);
        sort(j+1,end);
    }

    int partition(int start, int end){
        int pivot=nums[start];
        int i=start+1;
        int j=end;
        while(i<=j){
            while(i<=end && nums[i]<=pivot){
                i++;
            }
            while(j>=start &&nums[j]>pivot){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(i,j);
        }
        swap(start,j);
        return j;
    }

    void swap(int i, int j){
        if(i==j){
            return;
        }
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

09/22/2022更新： 不加random的quicksort已经AC不了了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    Random rand = new Random();
    
    public int[] sortArray(int[] nums) {
        // quick sort
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    private void quickSort(int[] arr, int start, int end) {
        if(end<=start){
            return;
        }
        // pick random elem, split to two arrs
        int index = partition(arr, start, end);
        quickSort(arr, start, index - 1);
        quickSort(arr, index + 1, end);
    }
    
    private int partition(int[] arr, int start, int end) {
        // partition [left, right]
        int index = rand.nextInt(end - start + 1) + start;
        swap(arr, index, end);
        int left = start;
        int right = end - 1;
        // [start, left-1] smaller than arr[end]
        // [left, right] unknown
        // [right, end - 1] larger than or equal to arr[end]
        while(left<=right) {
            if(arr[left]<arr[end]) {
                left++;
            } else {
                swap(arr, left, right);
                right--;
            }
        }
        swap(arr, left, end);
        return left;
    }
}

215. Kth Largest Element in an Array

找第k大的数，也就是将数组分为两部分，前部有n-k个元素，后部有k个元素，且前部元素均小于后部元素

而快排的partition返回值j，正好将数组分为[0, j-1] 和 [j+1, n-1] 两部分，且前部分有j个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int[] nums;
    public int findKthLargest(int[] nums, int k) {
        this.nums=nums;
        int lo=0;
        int hi=nums.length-1;
        int n=nums.length;
        while(lo<=hi){
            int j=partition(lo,hi);
            if(j<n-k){
                lo=j+1;
            }else if(j>n-k){
                hi=j-1;
            }else{
                return nums[j];
            }
        }
        return -1;
    }

    int partition(int start, int end){
        int pivot=nums[start];
        int i=start+1;
        int j=end;
        while(i<=j){
            while(i<=end && nums[i]<=pivot){
                i++;
            }
            while(j>=start && nums[j]>pivot){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(i,j);
        }
        swap(start,j);
        return j;
    }

    void swap(int i, int j){
        if(i==j){
            return;
        }
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
Random rand=new Random();
public int findKthLargest(int[] nums, int k) {
    int n=nums.length;
    int low=0;
    int high=n-1;
    while(low<=high){
        int j=partition(nums,low,high);
        if(j<n-k){
            low=j+1;
        }else if(j>n-k){
            high=j-1;
        }else{
            return nums[j];
        }
    }
    return -1;
}

int partition(int[] nums, int start, int end){
    int index=rand.nextInt(end-start+1)+start;
    swap(nums,start,index);
    int pivot=nums[start];
    int i=start+1;
    int j=end;
    //[start,i) <=pivot
    //[i,j] unknown
    //(j,end] >pivot
    while(i<=j){
        if(nums[j]>pivot){
            j--;
        }else{
            swap(nums,i++,j);
        }
    }
    swap(nums,start,j);
    return j;
}

void swap(int[] nums, int i, int j){
    if(i==j){
        return;
    }
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

新模板！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Random rand=new Random();
public int findKthLargest(int[] nums, int k) {
    int n=nums.length;
   quickSelect(nums,0,n-1,n-k);
    return nums[n-k];
}

void quickSelect(int[] nums, int left, int right, int k){
    if(left==right){
        return;
    }
    int pivotIndex=left+rand.nextInt(right-left+1);
    int pivot=partition(nums,left,right,pivotIndex);
    if(pivot==k){
        return;
    }
    if(k<pivot){
        quickSelect(nums,left,pivot-1,k);
    }else{
        quickSelect(nums,pivot+1,right,k);
    }
}

int partition(int[] nums, int left, int right, int pivot){
    int val=nums[pivot];
    swap(nums,right,pivot);
    int idx=left;
    for (int i = left; i <= right; i++) {
        if(nums[i]<val){
            swap(nums,idx++,i);
        }
    }
    swap(nums,idx,right);
    return idx;
}

void swap(int[] nums, int a, int b){
    if(a==b){
        return;
    }
    nums[a]^=nums[b];//a^b
    nums[b]^=nums[a];//b^a^b=a
    nums[a]^=nums[b];//a^b^a=b
}

Quick Selection

324. Wiggle Sort II

披着medium外皮的hard！

https://leetcode.cn/problems/wiggle-sort-ii/solution/yi-bu-yi-bu-jiang-shi-jian-fu-za-du-cong-onlognjia/#comment

快速选择算法与快速排序算法类似，在一次递归调用中，首先进行partition过程，即利用一个元素将原数组划分为两个子数组，然后将这一元素放在两个数组之间。两者区别在于快速排序接下来需要对左右两个子数组进行递归，而快速选择只需要对一侧子数组进行递归，所以快速选择的时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    Random random = new Random();

    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int x = (n + 1) / 2;
        int mid = x - 1;
        int target = findKthLargest(nums, n - mid);
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
            if (nums[k] > target) {
                while (j > k && nums[j] > target) {
                    j--;
                }
                swap(nums, k, j--);
            }
            if (nums[k] < target) {
                swap(nums, k, i++);
            }
        }
        int[] arr = nums.clone();
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
            nums[i] = arr[j];
            if (i + 1 < n) {
                nums[i + 1] = arr[k];
            }
        }
    }

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

    public int quickSelect(int[] a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }

    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

347. Top K Frequent Elements

桶排序更好！

设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。

把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequencyForNum = new HashMap<>();
    for (int num : nums) {
        frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
    }
    List<Integer>[] buckets = new ArrayList[nums.length + 1];
    for (int key : frequencyForNum.keySet()) {
        int frequency = frequencyForNum.get(key);
        if (buckets[frequency] == null) {
            buckets[frequency] = new ArrayList<>();
        }
        buckets[frequency].add(key);
    }
    List<Integer> topK = new ArrayList<>();
    for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
        if (buckets[i] == null) {
            continue;
        }
        if (buckets[i].size() <= (k - topK.size())) {
            topK.addAll(buckets[i]);
        } else {
            topK.addAll(buckets[i].subList(0, k - topK.size()));
        }
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = topK.get(i);
    }
    return res;
}

quickselect/quicksort 新模板：

  1. 换pivot到right
  2. for循环从left到right，若 < 则store
  3. 换right到store
  4. return store
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Map<Integer,Integer> map=new HashMap<>();
int[] unique;
Random rand=new Random();
public int[] topKFrequent(int[] nums, int k) {
    for (int num : nums) {
        map.put(num,map.getOrDefault(num,0)+1);
    }
    int n=map.size();
    unique=new int[n];
    int idx=0;
    for (Integer num : map.keySet()) {
        unique[idx++]=num;
    }
    quickSelect(0,n-1,n-k);
    return Arrays.copyOfRange(unique,n-k,n);
}

void quickSelect(int left, int right, int k){
    if(left>=right){
        return;
    }
    //[k,k+1,..,n-1]
    int pivotIndex=left+rand.nextInt(right-left+1);
    int pivot=partition(left,right,pivotIndex);
    if(pivot==k){
        return;
    }
    if(k<pivot){
        quickSelect(left,pivot-1,k);
    }else{
        quickSelect(pivot+1,right,k);
    }
}

int partition(int left, int right, int pivot){
    int pivotFreq=map.get(unique[pivot]);
    swap(right,pivot);
    int idx=left;
    for (int i = left; i <= right; i++) {
        if(map.get(unique[i])<pivotFreq){
            swap(idx++,i);
        }
    }
    swap(idx,right);
    return idx;
}

void swap(int a, int b){
    if(a==b){
        return;
    }
    int temp=unique[a];
    unique[a]=unique[b];
    unique[b]=temp;
}