Count of Smaller Numbers After Self(Hard)
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Examples
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
树状数组:复杂度将为O(NlgN)
private int lowbit(int x) {
return x&(-x);
}
private void update(int[] bit, int i, int val) {
for (; i < bit.length; i += lowbit(i))
bit[i] += val;
}
private int read(int[] bit, int i) {
int ans = 0;
for (; i > 0; i -= lowbit(i))
ans += bit[i];
return ans;
}
public List<Integer> countSmaller(int[] nums) {
int[] tmp = nums.clone();
Arrays.sort(tmp);
for (int i = 0; i < nums.length; i++)
nums[i] = Arrays.binarySearch(tmp, nums[i]);
int[] bit = new int[nums.length+1];
Integer[] ans = new Integer[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
ans[i] = read(bit, nums[i]);
update(bit, nums[i] + 1, 1);
}
return Arrays.asList(ans);
}
解法2：binary search
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return result;
List<Integer> sorted = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
int index = find(sorted, nums[i]);
result.add(index);
sorted.add(index,nums[i]);
}
Collections.reverse(result);//!!don't forget to reverse
return result;
}
public int find(List<Integer> sorted, int val) {
//if (sorted.size() == 0) return 0; no need
int lo = 0, hi = sorted.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sorted.get(mid) == val) {
while (mid - 1 >= 0 && sorted.get(mid - 1) == val) {
mid--;
}
return mid;
} else if (sorted.get(mid) < val) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return lo;
}