題目
給你一個數組 nums,對于其中每個元素 nums[i],請你統計數組中比它小的所有數字的數目。
換而言之,對于每個 nums[i] 你必須計算出有效的 j 的數量,其中 j 滿足 j != i 且 nums[j] < nums[i] 。
以數組形式傳回答案。
示例1:
輸入:nums = [8,1,2,2,3]
輸出:[4,0,1,1,3]
解釋:
對于 nums[0]=8 存在四個比它小的數字:(1,2,2 和 3)。
對于 nums[1]=1 不存在比它小的數字。
對于 nums[2]=2 存在一個比它小的數字:(1)。
對于 nums[3]=2 存在一個比它小的數字:(1)。
對于 nums[4]=3 存在三個比它小的數字:(1,2 和 2)。
示例2:
輸入:nums = [6,5,4,8]
輸出:[2,1,0,3]
輸入:nums = [7,7,7,7]
輸出:[0,0,0,0]
解題思路
代碼實作
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int n = nums.length;
int[][] data = new int[n][2];
for (int i = 0; i < n; i++) {
data[i][0] = nums[i];
data[i][1] = i;
}
Arrays.sort(data, new Comparator<int[]>() {
public int compare(int[] data1, int[] data2) {
return data1[0] - data2[0];
}
});
int[] ret = new int[n];
int prev = -1;
for (int i = 0; i < n; i++) {
if (prev == -1 || data[i][0] != data[i - 1][0]) {
prev = i;
}
ret[data[i][1]] = prev;
}
return ret;
}
}
複雜度分析
- 時間複雜度:O(NlogN),其中 N 為數組的長度。排序需要 O(NlogN) 的時間,随後需要 O(N) 時間來周遊。
- 空間複雜度:O(N)。因為要額外開辟一個數組。