原题
有n堆苹果,每堆苹果数量为a[i]个,给定m个数,每个数字为q[i],从左往右数,求第q[i]个苹果在第几堆苹果里面。输入:n表示有n堆苹果,然后依次输入每堆苹果的个数a[i],接着输入m表示一共需要计算m个苹果的位置,最后输入每个苹果的编号q[i]。输出:依次输出每个苹果的位置。样例如下:
输入:
5
2 7 3 4 9
3
1 25 11
输出:
1
5
3
AC代码(Java)
import java.util.Scanner;
public class Main {
public static int getBinarySearch(int[] arr, int k) {
if (arr == null) {
return -1;
} else {
int res = -1;
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (k > arr[middle]) {
left = middle + 1;
res = middle + 1;
} else if (k < arr[middle]) {
right = middle - 1;
res = middle;
} else {
res = middle;
break;
}
}
return res + 1;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] ai = new int[n];
for (int i = 0; i < ai.length; i++) {
ai[i] = scanner.nextInt();
}
int m = scanner.nextInt();
int[] qi = new int[m];
for (int i = 0; i < qi.length; i++) {
qi[i] = scanner.nextInt();
}
int[] sumArr = new int[n];
sumArr[0] = ai[0];
for (int i = 1; i < n; i++) {
sumArr[i] = sumArr[i - 1] + ai[i];
}
int[] ansArr = new int[m];
for (int i = 0; i < qi.length; i++) {
ansArr[i] = getBinarySearch(sumArr, qi[i]);
}
for (int i = 0; i < ansArr.length; i++) {
System.out.println(ansArr[i]);
}
}
}
思考
此题要想得出正确的输出其实不难,暴力解也能输出。但在实际考试过程中提交代码时,暴力解法通过率仅为30%。暴力解法的思路无非是双循环,然后依次的去判断每个qi在ai中的位置,此时时间复杂度则为O(mn)。
现在的互联网公司在笔、面试题中对于算法题目的考察,其实很多题目就是考对问题处理的时间复杂度,没完全通过的原因一般都是因为时间复杂度太大导致的,所以在笔试过程中如果说没完全通过,可以考虑优化时间复杂度。比如说复杂点的题目是否可以做成动态规划,简单点的题目是否用对了时间复杂度更低的方法。找准了思路,问题解决的目的性就可以变得很明确,可以快速的找到对应的方法去解决。比如经典的topK问题,一种解决思路就是去找一个时间复杂度尽可能低的算法去对k个数据进行排序比较,在这种场景下,自然就想到了堆排,大/小顶堆去实现。
此题其实也不例外,当你用暴力法去解的时候。首先要思考的问题就是怎么去和数组的前几个数去比较,以确定q[i]的位置。此时其实有两种思路,一种是把a[j]前几个依次加起来,直到找到q[i]小于等于a[j]的前j个数组和的位置即为答案。另一种就是减法的思想,当q[i]大于a[j]时候,那么q[i]-a[j],j++,直到找到q[i]<=a[j],此时的位置即为答案。对于第一种思路,其实可以有优化的空间,因为你在每次比较q[i]的时候,其实都计算了a[j]的前j个数的和,这样就造成了计算重复,我们可以定义一个数组sumArr去储存前a[j]中前j数的和,这样我们就不必每次都去计算这个数值了。
当我们定义完这个数组时,我们发现这个数组是一个有序递增数组。问题其实就转化成在一个有序数组中去查找目标数所在的区间,两个方法。
1. 遍历数组,时间复杂度为O(n)
2. 二分查找,时间复杂度为O(logn)
很明显,果断选择二分查找,此时题目的时间复杂度则将为O(mlogn)。这样就可以顺利AC。
网友评论