成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

2json / 2216人閱讀

摘要：由于這道題目不是查找而是選擇第一個(gè)的數(shù)的位置，所以語(yǔ)句里面可以把和歸為同一個(gè)分支，因?yàn)榇嬖诎貜?fù)數(shù)的情況，所以要和一樣，指針前移替換。那么另一個(gè)分支，除了將后移，還要更新返回值。約束條件為的兩種寫法

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

由于這道題目不是查找==而是選擇第一個(gè)>(num)的數(shù)的位置，所以while語(yǔ)句里面可以把>和=歸為同一個(gè)分支>=，因?yàn)?==)存在包含重復(fù)數(shù)(duplicate)的情況，所以要和>一樣，end指針前移替換mid。
那么另一個(gè)分支<，除了將start后移，還要更新返回值res。

第二點(diǎn)，如果while循環(huán)的約束條件是start < end，假如循環(huán)到最后start = end - 1，并且num就在end呢？這時(shí)應(yīng)該返回res = start + 1，推測(cè)前一步，start = end - 2的時(shí)候，end的前移只能到mid為止，不能是mid - 1，否則就跳過(guò)了可能為所求結(jié)果的mid。
所以這個(gè)分支這樣寫：

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

第三點(diǎn)，順理成章，while (start <= end)的情況下，end = mid - 1是可行的：在最后一步end與start重合，return的是（指針start向后移動(dòng)的）start位置，或者（指針end向前移動(dòng)的）與start重合位置的下一個(gè)位置。
約束條件為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.

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65527.html

相關(guān)文章

  • [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 評(píng)論0 收藏0

  • [LintCode] Majority Number I II III

    摘要：遍歷整個(gè)數(shù)組，用一個(gè)計(jì)數(shù)器，找出超過(guò)整個(gè)數(shù)組長(zhǎng)度二分之一的那個(gè)數(shù)。規(guī)則是當(dāng)前數(shù)等于，計(jì)數(shù)器加否則，計(jì)數(shù)器減。當(dāng)?shù)拇笮〉扔跁r(shí)，統(tǒng)計(jì)中所有的，并將所有對(duì)應(yīng)的減，若被減為，就從中移除這對(duì)鍵值。 Majority Number I Problem Given an array of integers, the majority number is the number that occurs ...

    sPeng 評(píng)論0 收藏0

  • [LintCode] Find the Missing Number [三種方法]

    摘要：求和相減是先求出到這個(gè)等差數(shù)列的和，再減去實(shí)際數(shù)組的和，就是缺失的數(shù)，第二種方法是，只要先按順序排列好，用二分法找到第一個(gè)和不相等的數(shù)就可以了。二分法求和相減法共個(gè)數(shù)，多加了一個(gè)異或法 Problem Given an array contains N numbers of 0 .. N, find which number doesnt exist in the array. Exa...

    liaoyg8023 評(píng)論0 收藏0

  • [LintCode] Flip Bits

    摘要：的二進(jìn)制補(bǔ)碼就是個(gè)，因此這道題一定要考慮正負(fù)號(hào)的問(wèn)題。然后去檢查的二進(jìn)制包含多少個(gè)，方法是對(duì)的每一位除以取余。如果為，就說(shuō)明那一位為，即和在那一位不同，需要進(jìn)行轉(zhuǎn)換。每次取余之后，減小為二分之一，刪除已經(jīng)檢查過(guò)的高位。 Problem Determine the number of bits required to flip if you want to convert integer...

    joyvw 評(píng)論0 收藏0

  • [LintCode] Backpack I II III IV V VI [背包六問(wèn)]

    摘要：?jiǎn)未芜x擇最大體積動(dòng)規(guī)經(jīng)典題目，用數(shù)組表示書包空間為的時(shí)候能裝的物品最大容量。注意的空間要給，因?yàn)槲覀円蟮氖堑趥€(gè)值，否則會(huì)拋出。依然是以背包空間為限制條件，所不同的是取的是價(jià)值較大值，而非體積較大值。 Backpack I Problem 單次選擇+最大體積 Given n items with size Ai, an integer m denotes the size of a b...

    sutaking 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<