題目
315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)
內(nèi)容
給定一個(gè)整數(shù)數(shù)組 nums莽鸿，按要求返回一個(gè)新數(shù)組 counts。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是 nums[i] 右側(cè)小于 nums[i] 的元素的數(shù)量。
示例:
輸入: [5,2,6,1]
輸出: [2,1,1,0]
解釋:
5 的右側(cè)有 2 個(gè)更小的元素 (2 和 1).
2 的右側(cè)僅有 1 個(gè)更小的元素 (1).
6 的右側(cè)有 1 個(gè)更小的元素 (1).
1 的右側(cè)有 0 個(gè)更小的元素.
題解
計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)，也就是我們可以對(duì) 第i位的num右側(cè)的數(shù)列進(jìn)行排序 然后插入nums[i] 插入位置就是 右側(cè)小于當(dāng)前元素的個(gè)數(shù)，在尋找插入位置時(shí)直接循環(huán)查找會(huì)超時(shí)，所以我們?cè)谶@部分做二分查找 所以最差時(shí)間是logn! 而直接循環(huán)查找的話最差 1/2+1/2n^2*.
代碼
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
if (nums.length == 0)
return new ArrayList<>();
int len = nums.length;
Integer[] maxn = new Integer[nums.length];
maxn[len - 1] = 0;
int j = 0;
list.add(nums[len - 1]);
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > list.get(list.size() - 1)) {
maxn[i] = list.size();
list.add(nums[i]);
} else {
int l = 0;
int r = list.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[i] > list.get(m)) {
l = m + 1;
} else {
r = m;
}
}
list.add(r, nums[i]);
maxn[i] = r;
}
}
return Arrays.asList(maxn);
}
結(jié)果
image.png
