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

2json 发布于2019-08-14 15:16 / 2048人阅读

摘要：由于这道题目不是查找而是选择第一个的数的位置，所以语句里面可以把和归为同一个分支，因为存在包含重复数的情况，所以要和一样，指针前移替换。那么另一个分支，除了将后移，还要更新返回值。约束条件为的两种写法

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;
        }
    }

    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.

Just loop.

Sort and binary search.

Build Segment Tree and Search.

Solution

Muggle

public class Solution {
    public ArrayList countOfSmallerNumber(int[] A, int[] queries) {
        ArrayList res = new ArrayList();
        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 countOfSmallerNumber(int[] A, int[] queries) {
        // write your code here
        ArrayList res = new ArrayList();
        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 countOfSmallerNumber(int[] A, int[] queries) {
        ArrayList res = new ArrayList();
        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;
    }
}

私有云 GPU服务器 Smaller LintCode LintCode134_LRU Count

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65527.html

[LintCode] 3Sum Smaller

Problem Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target) return 0; int count = 0; for (int i = 0; i < nums.length-2; i++) { ...

AprilJ 2019-08-15 18:09 评论0 收藏0
[LintCode] Majority Number I II III

摘要：遍历整个数组，用一个计数器，找出超过整个数组长度二分之一的那个数。规则是当前数等于，计数器加否则，计数器减。当的大小等于时，统计中所有的，并将所有对应的减，若被减为，就从中移除这对键值。 Majority Number I Problem Given an array of integers, the majority number is the number that occurs ...

sPeng 2019-08-14 15:43 评论0 收藏0
[LintCode] Find the Missing Number [三种方法]

摘要：求和相减是先求出到这个等差数列的和，再减去实际数组的和，就是缺失的数，第二种方法是，只要先按顺序排列好，用二分法找到第一个和不相等的数就可以了。二分法求和相减法共个数，多加了一个异或法 Problem Given an array contains N numbers of 0 .. N, find which number doesnt exist in the array. Exa...

liaoyg8023 2019-08-14 15:20 评论0 收藏0
[LintCode] Flip Bits

摘要：的二进制补码就是个，因此这道题一定要考虑正负号的问题。然后去检查的二进制包含多少个，方法是对的每一位除以取余。如果为，就说明那一位为，即和在那一位不同，需要进行转换。每次取余之后，减小为二分之一，删除已经检查过的高位。 Problem Determine the number of bits required to flip if you want to convert integer...

joyvw 2019-08-14 15:21 评论0 收藏0
[LintCode] Backpack I II III IV V VI [背包六问]

摘要：单次选择最大体积动规经典题目，用数组表示书包空间为的时候能装的物品最大容量。注意的空间要给，因为我们要求的是第个值，否则会抛出。依然是以背包空间为限制条件，所不同的是取的是价值较大值，而非体积较大值。 Backpack I Problem 单次选择+最大体积 Given n items with size Ai, an integer m denotes the size of a b...

sutaking 2019-08-14 14:31 评论0 收藏0