大家好,我是周一。
在上一篇归并排序中,咱们讲了归并排序的基本概念、merge(合并)过程等,明天趁热打铁,咱们来说说应用归并排序的一些常见面试题。
一、小和问题
1、题目形容:
在一个数组中,每一个数右边比以后数小的数累加起来,叫做这个数组的小和。求一个给定数组的小和。
2、例子:
数组为:[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
3、思路:
找每一个数左边比以后数大的个数,(个数 * 以后数) 的累加和就是后果。
这咋和归并排序分割上的呢,认真想想,在左组和右组 merge 的时候,会比拟数的大小,这时就能够在右组找到比左组以后数大的个数。
4、具体的参考代码:
/**
* 小和问题:在一个数组中,每一个数右边比以后数小的数累加起来,叫做这个数组的小和。要求工夫复杂度 O(N*logN)
*
* @author Java 和算法学习:周一
*/
public class SmallSum {public static int smallSum(int[] arr) {if (arr == null || arr.length < 2) {return 0;}
return process(arr, 0, arr.length - 1);
}
private static int process(int[] arr, int l, int r) {if (l == r) {return 0;}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
private static int merge(int[] arr, int l, int mid, int r) {int[] help = new int[r - l + 1];
int i = 0;
int pL = l;
int pR = mid + 1;
int res = 0;
while (pL <= mid && pR <= r) {
// 当左组的数小于右组的数时,以后右组的个数 * 以后数 的累加和 即是小和的后果
// 认真和归并排序比拟,发现就多了此处的代码。惟一的区别是,// 等于的时候拷贝右组的,因为要在右组中找出比左组大的个数,必定不能先拷贝左组的,不然咋找出个数
res += arr[pL] < arr[pR] ? (r - pR + 1) * arr[pL] : 0;
help[i++] = arr[pL] < arr[pR] ? arr[pL++] : arr[pR++];
}
while (pL <= mid) {help[i++] = arr[pL++];
}
while (pR <= r) {help[i++] = arr[pR++];
}
for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];
}
return res;
}
/**
* 对数器办法
*/
public static int comparator(int[] arr) {
int res = 0;
for (int i = 1; i < arr.length; i++) {for (int j = 0; j < i; j++) {res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
public static void main(String[] args) {
int maxSize = 100;
int maxValue = 100;
int testTimes = 100000;
boolean isSuccess = true;
for (int i = 0; i < testTimes; i++) {int[] arr1 = generateArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (smallSum(arr1) != comparator(arr2)) {printArray(arr1);
printArray(arr2);
isSuccess = false;
break;
}
}
System.out.println(isSuccess ? "Nice" : "Error");
}
//------------------------------------------ TEST METHODS ----------------------------------------------
public static int[] generateArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {if (arr == null) {return null;}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {res[i] = arr[i];
}
return res;
}
public static void printArray(int[] arr) {if (arr == null) {return;}
for (int value : arr) {System.out.print(value + " ");
}
System.out.println();}
}
二、逆序对问题
1、题目形容:
设有一个数组 [a1, a2, a3,… an],对于数组中任意两个元素 ai,aj,若 i <j,ai>aj,则阐明 ai 和 aj 是一对逆序对。求一个给定数组的逆序对个数。
2、例子:
3 5 2 1 0 4 9
所有逆序对是:(3,2),(3,1),(3,0),(5,2),(5,1),(5,0),(5,4),(2,1),(2,0),(1,0)。逆序对个数为 10。
3、思路:
合并的时候,从右往左合并,(此时右组地位 – mid 地位) 的累加和 即是逆序对个数。
这又咋和归并排序分割上的呢,认真想想,在左组和右组 merge 的时候,会比拟数的大小,然而我要找到的是左边更小的,所以能够采纳从右往左合并的形式;同时在解决相等的时候,须要先拷贝右组的,这样能力精确找出右组小的个数。
4、具体的参考代码:
/**
* 逆序对问题:设有一个数组 [a1, a2, a3,... an],对于数组中任意两个元素 ai,aj,若 i <j 且 ai>aj,则阐明 ai 和 aj 是一对逆序对。* 求一个给定数组的逆序对个数。*
* @author Java 和算法学习:周一
*/
public class ReversePair {public static int reversePairNum(int[] arr) {if (arr == null || arr.length < 2) {return 0;}
return process(arr, 0, arr.length - 1);
}
private static int process(int[] arr, int l, int r) {if (l == r) {return 0;}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
private static int merge(int[] arr, int l, int mid, int r) {
// 辅助数组
int[] help = new int[r - l + 1];
// 辅助下标,因为从右往左合并,所以下标为数组最大值
int i = help.length - 1;
// 同理,左组第一个数地位为 mid
int pL = mid;
// 右组第一个数为最初一个
int pR = r;
// 逆序对个数
int num = 0;
while (pL >= l && pR >= (mid + 1)) {// 找到右组第一个比左组小的数,则以后满足要求的逆序对个数为 (pR - (mid + 1) + 1) 即是 (pR - mid)
num += arr[pL] > arr[pR] ? (pR - mid) : 0;
// 从右往左拷贝,相等的拷贝右组的
help[i--] = arr[pL] > arr[pR] ? arr[pL--] : arr[pR--];
}
// 左组和右组有且仅有一个未拷贝完,所以以下两个循环只会执行其中一个
while (pL >= l) {help[i--] = arr[pL--];
}
while (pR > mid) {help[i--] = arr[pR--];
}
// 拷贝回原数组
for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];
}
return num;
}
/**
* 对数器用于测试
*/
public static int comparator(int[] arr) {
int num = 0;
for (int i = 0; i < arr.length; i++) {for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[i]) {num++;}
}
}
return num;
}
public static void main(String[] args) {
int testTime = 1000000;
int maxSize = 100;
int maxValue = 100;
boolean isSuccess = true;
for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (reversePairNum(arr1) != comparator(arr2)) {printArray(arr1);
printArray(arr2);
isSuccess = false;
break;
}
}
System.out.println(isSuccess ? "Nice" : "Error");
}
//--------------------------------------- 辅助测试的办法 ---------------------------------------------
public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {if (arr == null) {return null;}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {res[i] = arr[i];
}
return res;
}
public static void printArray(int[] arr) {if (arr == null) {return;}
for (int value : arr) {System.out.print(value + " ");
}
System.out.println();}
}
OK,明天就临时先说利用归并排序解决 小和 和逆序对 问题的题目。
有时候,各种排序算法把握它自身并不难,难的是你可能充沛了解它的过程和精华,更难的是在真正遇到理论题目的时候,可能想到用这种排序算法来解决它。所以,算法无捷径,唯有多练习,在有足够多的量,积攒质变,而后能力迎来量变,那时能力信手拈来,加油。