[LintCode] Count of Smaller Number [二分法的活用]

108 查看

Problem

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller than the given integer.

Example

For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]

Note

由于这道题目不是查找==而是选择第一个>(num)的数的位置,所以while语句里面可以把>=归为同一个分支>=,因为(==)存在包含重复数(duplicate)的情况,所以要和>一样,end指针前移替换mid。
那么另一个分支<,除了将start后移,还要更新返回值res。

第二点,如果while循环的约束条件是start < end,假如循环到最后start = end - 1,并且num就在end呢?这时应该返回res = start + 1,推测前一步,start = end - 2的时候,end的前移只能到mid为止,不能是mid - 1,否则就跳过了可能为所求结果的mid。
所以这个分支这样写:

    while (start < end) {
        int mid = (start + end) / 2;
        if (A[mid] >= num) end = mid;
        else {
            start = mid + 1;
            res = mid + 1;
        }
    }

第三点,顺理成章,while (start <= end)的情况下,end = mid - 1是可行的:在最后一步end与start重合,return的是(指针start向后移动的)start位置,或者(指针end向前移动的)与start重合位置的下一个位置。
约束条件为start <= end的两种写法:
1.

    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] >= num) end = mid - 1;
        else {
            start = mid + 1;
            res = mid + 1;
        }
    }

2.

    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] < num) start = mid + 1;
        else {
            end = mid - 1;
            res = mid;
        }
    }

Challenge

Could you use three ways to do it.

  1. Just loop.

  2. Sort and binary search.

  3. Build Segment Tree and Search.

Solution

Muggle

public class Solution {
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            for (int i = 0; i < queries.length; i++) {
                res.add(0);
            }
            return res;
        }
        Arrays.sort(A);
        int index;
        for (int num: queries) {
            for (int i = 0; i < A.length; i++) {
                if (num <= A[i]) {
                    index = i;
                    res.add(index);
                    break;
                }
            }
        }
        return res;
    }
}

Binary Search

(1)

public class Solution {
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        Arrays.sort(A);
        for (int num: queries) {
            res.add(helper(A, num));
        }
        return res;
    }
    public int helper(int[] A, int num) {
        int start = 0, end = A.length-1;
        int res = 0;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] < num) start = mid + 1;
            else {
                end = mid - 1;
                res = mid;
            }
        }
        return res;
    }
}

(2)

public class Solution {
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Arrays.sort(A);
        for (int num: queries) {
            res.add(helper(A, num));
        }
        return res;
    }
    public int helper(int[] A, int num) {
        int start = 0, end = A.length-1;
        int res = 0;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] >= num) end = mid - 1;
            else {
                start = mid + 1;
                res = mid + 1;
            }
        }
        return res;
    }
}

2020 - 知识虫 - 我的知识库 重庆启连科技有限公司 渝ICP备16002641号-2

渝公网安备 50010702501581号