美文网首页
关于二分查找的一些思考,网易2019秋招笔试题。

关于二分查找的一些思考,网易2019秋招笔试题。

作者: 今年小学一年级 | 来源:发表于2018-08-12 02:24 被阅读0次

    原题

      有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。

    相关文章

      网友评论

          本文标题:关于二分查找的一些思考,网易2019秋招笔试题。

          本文链接:https://www.haomeiwen.com/subject/sebjbftx.html