資訊專欄INFORMATION COLUMN
摘要：由于這道題目不是查找而是選擇第一個的數(shù)的位置，所以語句里面可以把和歸為同一個分支，因為存在包含重復(fù)數(shù)的情況，所以要和一樣，指針前移替換。那么另一個分支，除了將后移，還要更新返回值。約束條件為的兩種寫法
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.
ExampleFor array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]
Note由于這道題目不是查找==而是選擇第一個>(num)的數(shù)的位置，所以while語句里面可以把>和=歸為同一個分支>=，因為(==)存在包含重復(fù)數(shù)(duplicate)的情況，所以要和>一樣，end指針前移替換mid。
那么另一個分支<，除了將start后移，還要更新返回值res。
第二點，如果while循環(huán)的約束條件是start < end，假如循環(huán)到最后start = end - 1，并且num就在end呢？這時應(yīng)該返回res = start + 1，推測前一步，start = end - 2的時候，end的前移只能到mid為止，不能是mid - 1，否則就跳過了可能為所求結(jié)果的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.
Just loop.
Sort and binary search.
Build Segment Tree and Search.
SolutionMuggle
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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65527.html
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++) { ...
摘要：遍歷整個數(shù)組，用一個計數(shù)器，找出超過整個數(shù)組長度二分之一的那個數(shù)。規(guī)則是當前數(shù)等于，計數(shù)器加否則，計數(shù)器減。當?shù)拇笮〉扔跁r，統(tǒng)計中所有的，并將所有對應(yīng)的減，若被減為，就從中移除這對鍵值。 Majority Number I Problem Given an array of integers, the majority number is the number that occurs ...
摘要：求和相減是先求出到這個等差數(shù)列的和，再減去實際數(shù)組的和，就是缺失的數(shù)，第二種方法是，只要先按順序排列好，用二分法找到第一個和不相等的數(shù)就可以了。二分法求和相減法共個數(shù)，多加了一個異或法 Problem Given an array contains N numbers of 0 .. N, find which number doesnt exist in the array. Exa...
摘要：的二進制補碼就是個，因此這道題一定要考慮正負號的問題。然后去檢查的二進制包含多少個，方法是對的每一位除以取余。如果為，就說明那一位為，即和在那一位不同，需要進行轉(zhuǎn)換。每次取余之后，減小為二分之一，刪除已經(jīng)檢查過的高位。 Problem Determine the number of bits required to flip if you want to convert integer...
摘要：單次選擇最大體積動規(guī)經(jīng)典題目，用數(shù)組表示書包空間為的時候能裝的物品最大容量。注意的空間要給，因為我們要求的是第個值，否則會拋出。依然是以背包空間為限制條件，所不同的是取的是價值較大值，而非體積較大值。 Backpack I Problem 單次選擇+最大體積 Given n items with size Ai, an integer m denotes the size of a b...
閱讀 1040·2023-04-25 19:17
閱讀 2377·2021-09-10 11:26
閱讀 2083·2019-08-30 15:54
閱讀 3564·2019-08-30 15:53
閱讀 2830·2019-08-30 11:20
閱讀 3549·2019-08-29 15:12
閱讀 1362·2019-08-29 13:16
閱讀 2499·2019-08-26 12:19
