一、基础 - 归并排序
归并排序思想十分简单，但是利用归并排序的变形，可以解决一些看似较为复杂的问题
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 {
public void mergeSort(int[] array) {
if (array == null || array.length < 2) return ;
mergeSort(array,0,array.length - 1);
}
public void mergeSort(int[] array,int left,int right){
if (right == left) return;
int mid = left + ((right - left) >> 1);
mergeSort(array,left,mid);
mergeSort(array,mid + 1,right);
merge(array,left,mid,right);
}
public void merge(int[] array,int left,int mid,int right){
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;
while (p1 <= mid && p2 <= right){
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid){
help[i++] = array[p1++];
}
while (p2 <= right){
help[i++] = array[p2++];
}
for (int j : help) {
array[left++] = j;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = new int[]{1,3,4,2,5};
solution.mergeSort(nums);
System.out.println(nums);
}
}
|
二、拓展
小和问题
问题描述：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：
求数组 [1,3,4,2,5] 的小和
分析：
3 左边比 3 小的数，1
4 左边比 4 小的数，1、3
2 左边比 2 小的数，1
5 左边比 5 小的数，1、3、4、2
所以小和为 1+1+3+1+1+3+4+2=16
求小和算法：
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
| class Solution {
public int mergeSort(int[] array) {
if (array == null || array.length < 2) return 0;
return mergeSort(array,0,array.length - 1);
}
public int mergeSort(int[] array,int left,int right){
if (right == left) return 0;
int mid = left + ((right - left) >> 1);
int leftSum = mergeSort(array,left,mid);
int rightSum = mergeSort(array,mid + 1,right);
return leftSum + rightSum + merge(array,left,mid,right);
}
public int merge(int[] array,int left,int mid,int right){
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;
int result = 0;
while (p1 <= mid && p2 <= right){
result += array[p1] < array[p2] ? (right - p2 + 1) * array[p1] : 0;
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid){
help[i++] = array[p1++];
}
while (p2 <= right){
help[i++] = array[p2++];
}
for (int j : help) {
array[left++] = j;
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = new int[]{1,3,4,2,5};
System.out.println(solution.mergeSort(nums));
}
}
|
总结：
小和问题是经典的归并排序变形问题，与此类似的还有逆序对问题
逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对（个数）。
仅需改动核心步骤即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
while (p1 <= mid && p2 <= right){
if(array[p1] > array[p2]){
for(int i=p1;i<mid;i++){
System.out.println(array[p1]+","+array[p2]);
}
}
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
|
逆序对与小和问题本质一样，除此之外，还有荷兰国旗问题，是小和问题的轻微进阶版本
荷兰国旗问题
给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于 num 的数放在数组的右边。要求额外空间复杂度 O (1)，时间复杂度 O (N)
返回值含义： 一定会返回一个长度为 2 的数组，等于区域的左边界和右边界（也就是相等区域的边界范围 ）
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
| class Solution {
public int[] partition(int[] arr, int left, int right, int num) {
int less = left - 1;
int more = right + 1;
while (left < more){
if (arr[left] < num){
swap(arr,left++,++less);
}else if (arr[left] > num){
swap(arr,--more,left);
}else {
left++;
}
}
return new int[]{less + 1,more - 1};
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = new int[]{3,5,0,3,4,5,2,6,9,6,1};
solution.partition(nums,0,nums.length - 1,5);
System.out.println(solution.partition(nums,0,nums.length - 1,5));
}
}
|
参考：
【1】认识认识 O (NlogN) 的排序 | 左程云算法笔记
