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

2json 發布于2019-08-14 15:16 / 2212人閱讀

摘要：由于這道題目不是查找而是選擇第一個的數的位置，所以語句里面可以把和歸為同一個分支，因為存在包含重復數的情況，所以要和一樣，指針前移替換。那么另一個分支，除了將后移，還要更新返回值。約束條件為的兩種寫法

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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