1 归并排序
01 递归实现
由
估计递归时间复杂度
public static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int left, int right) {if (left == right) {return;}int mid = left + ((right - left) >> 1);process(arr, left, mid);process(arr, mid + 1, right);merge(arr, left, mid, right);}public static void merge(int[] arr, 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++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid) {help[i++] = arr[p1++];}while (p2 <= right) {help[i++] = arr[p2++];}for (int j = 0; j < help.length; j++) {arr[left + j] = help[j];}}
02 迭代实现
public static void mergeSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int mergeSize = 1;int length = arr.length;while (mergeSize < length) {int left = 0;while (left < length) {if (mergeSize > length - left) {break;}int mid = left + mergeSize - 1;int right = mid + Math.min(mergeSize, length - mid - 1);merge(arr, left, mid, right);left = right + 1;}if (mergeSize > (left >> 1)) {break;}mergeSize <<= 1;}}public static void merge(int[] arr, 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++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid) {help[i++] = arr[p1++];}while (p2 <= right) {help[i++] = arr[p2++];}for (int j = 0; j < help.length; j++) {arr[left + j] = help[j];}}
2 应用归并的几道算法题
题目1：小和问题
在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
例子： [1,3,4,2,5]
1左边比1小的数：没有
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
//在一个数组中，一个数左边比它小的数的总和，叫数的小和，
// 所有数的小和累加起来，叫数组小和。求数组小和
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 1) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
public static int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int ans = 0;
int p1 = left;
int p2 = mid + 1;
int i = 0;
while (p1 <= mid && p2 <= right) {
ans += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= right) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
return ans;
}
题目2：逆序对
在一个数组中，任何一个前面的数a，和任何一个后面的数b，如果(a,b)是降序的，就称为逆序对
返回数组中所有的逆序对数量
//在一个数组中，任何一个前面的数a，和任何一个后面的数b，
//如果(a,b)是降序的，就称为逆序对;返回数组中所有的逆序对个数
public static int reversePair(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
public static int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int p1 = mid;
int p2 = right;
int i = help.length - 1;
int ans = 0;
while (p1 >= left && p2 >= mid + 1) {
ans += arr[p1] > arr[p2] ? p2 - mid : 0;
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= left) {
help[i--] = arr[p1--];
}
while (p2 >= mid + 1) {
help[i--] = arr[p2--];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
return ans;
}
题目3：在一个数组中，对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0，2
0的后面没有
2的后面没有
所以总共有5个
01 算法1
//在一个数组中，对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
public static int biggerThanRightTwice(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
public static int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int p1 = mid;
int p2 = right;
int i = help.length - 1;
int ans = 0;
while (p1 >= left && p2 >= mid + 1) {
ans += arr[p1] > arr[p2] * 2 ? p2 - mid : 0;
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= left) {
help[i--] = arr[p1--];
}
while (p2 >= mid + 1) {
help[i--] = arr[p2--];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
return ans;
}
02 算法2
public static int merge2(int[] arr, int left, int mid, int right) {
int ans = 0;
int windR = mid + 1;
for (int i = left; i <= mid; i++) {
while (windR <= right && arr[i] > (arr[windR] * 2)) {
windR++;
}
ans += (windR - mid - 1);
}
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= right) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[left + i] = help[i];
}
return ans;
}
题目4：给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在[lower,upper]范围上
leetcoed:https://leetcode.com/problems/count-of-range-sum/
//给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在[lower,upper]范围上
public static int countRangeSum(int[] nums, int lower, int upper) {
if (nums == null || nums.length < 1) {
return 0;
}
//sum数组为arr数组前缀和数组,即sum[i]=arr[0]+arr[1]+...+arr[i]
long[] sum = new long[nums.length];
sum[0] = nums[0];
for (int i = 1; i < sum.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
return process(sum, 0, sum.length - 1, lower, upper);
}
public static int process(long[] sum, int left, int right, int lower, int upper) {
if (left == right) {
return sum[left] >= lower && sum[left] <= upper ? 1 : 0;
}
int mid = left + ((right-left) >> 1);
return process(sum, left, mid, lower, upper) + process(sum, mid + 1, right, lower, upper) + merge(sum, left, mid, right, lower, upper);
}
public static int merge(long[] sum, int left, int mid, int right, int lower, int upper) {
//求以下标x结尾的满足条件的数组，即时0~x-1的有多少前缀和sum[i]在(sum[x]-upper,sum[x]-lower]区间
//满足条件的范围
int ans = 0;
//[l,r)
int l = left;
int r = left;
for (int i = mid + 1; i <= right; i++) {
long newLower = sum[i] - upper;
long newUpper = sum[i] - lower;
while (r <= mid && sum[r] <= newUpper) {
r++;
}
while (l <= mid && sum[l] < newLower) {
l++;
}
ans += (r - l);
}
int p1 = left;
int p2 = mid + 1;
long[] help = new long[right-left+1];
int i = 0;
while (p1 <= mid && p2 <= right) {
help[i++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
}
while (p1 <= mid) {
help[i++] = sum[p1++];
}
while (p2 <= right) {
help[i++] = sum[p2++];
}
for (i = 0; i < help.length; i++) {
sum[left + i] = help[i];
}
return ans;
}
若有收获，就点个赞吧
0 人点赞
