315.Count-of-Smaller-Numbers-After-Self
315. Count of Smaller Numbers After Self
题目地址
https://leetcode.com/problems/count-of-smaller-numbers-after-self/
题目描述
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].
Example:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.代码
Approach #0 Binary Indexed Tree
class Solution {
class FenwickTree {
private int[] sums;
public FenwickTree(int n) {
sums = new int[n + 1];
}
public void update(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += lowbit(i);
}
}
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private int lowbit(int x) {
return x & -x;
}
};
public List<Integer> countSmaller(int[] nums) {
int[] sorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted);
Map<Integer, Integer> ranks = new HashMap();
int rank = 0;
for (int i = 0; i < sorted.length; i++) {
if (i == 0 || sorted[i] != sorted[i - 1]) {
ranks.put(sorted[i], ++rank);
}
}
FenwickTree tree = new FenwickTree(ranks.size());
List<Integer> ans = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i--) {
int sum = tree.query(ranks.get(nums[i]) - 1);
ans.add(sum);
tree.update(ranks.get(nums[i]), 1);
}
Collections.reverse(ans);
return ans;
}
}Approach #1 BST
Every node will maintain a val sum recording the total of number on it's left bottom side, dup counts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:
1(0, 1)
\
6(3, 1)
/
2(0, 2)
\
3(0, 1)class Solution {
class Node {
Node left, right;
int val, sum, dup = 1;
public Node(int v, int s) {
val = v;
sum = s;
}
}
public List<Integer> countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
Node root = null;
for (int i = nums.length - 1; i >= 0; i--) {
root = insert(nums[i], root, ans, i, 0);
}
return Arrays.asList(ans);
}
private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
if (node == null) {
node = new Node(num, 0);
ans[i] = preSum;
} else if (node.val == num) {
node.dup++;
ans[i] = preSum + node.sum;
} else if (num < node.val) { // left
node.sum++;
node.left = insert(num, node.left, ans, i, preSum);
} else { // right
// num > node.val
node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
}
return node;
}
}Approach #2 Merge Sort
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
int[] count = new int[nums.length];
int[] indexes = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
indexes[i] = i;
}
mergesort(nums, indexes, 0, nums.length - 1, count);
for (int i = 0; i < count.length; i++) {
res.add(count[i]);
}
return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end, int[] count){
if (end <= start) return;
int mid = (start + end) / 2;
mergesort(nums, indexes, start, mid, count);
mergesort(nums, indexes, mid + 1, end, count);
merge(nums, indexes, start, end, count);
}
private void merge(int[] nums, int[] indexes, int start, int end, int[] count) {
int mid = (start + end) / 2;
int left_index = start;
int right_index = mid + 1;
int rightcount = 0;
int[] new_indexes = new int[end - start + 1];
int sort_index = 0;
while (left_index <= mid && right_index <= end) {
if (nums[indexes[right_index]] < nums[indexes[left_index]]) {
new_indexes[sort_index] = indexes[right_index];
rightcount++;
right_index++;
} else {
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
}
sort_index++;
}
while (left_index <= mid){
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
sort_index++;
}
while (right_index <= end){
new_indexes[sort_index] = indexes[right_index];
right_index++;
sort_index++;
}
for (int i = start; i <= end; i++){
indexes[i] = new_indexes[i - start]; // ？
}
}
}Approach #3 Merge Sort
class Solution {
public List<Integer> countSmaller(int[] nums) {
int[] res = new int[nums.length];
int[] index = new int[nums.length];
for (int i = 0; i < res.length; i++) {
index[i] = i;
}
mergeSort(nums, index, 0, nums.length - 1, res);
List<Integer> list = new LinkedList<>();
for (int i: res) {
list.add(i);
}
return list;
}
private void mergeSort(int[] nums, int[] index, int l, int r, int[] res) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
mergeSort(nums, index, l, mid, res);
mergeSort(nums, index, mid + 1, r, res);
merge(nums, index, l, mid, mid + 1, r, res);
}
private void merge(int[] nums, int[] index, int l1, int r1, int l2, int r2, int[] res) {
int start = l1;
int[] tmp = new int[r2 - l1 + 1];
int count = 0;
int p = 0;
while (l1 <= r1 || l2 <= r2) {
if (l1 > r1) {
tmp[p++] = index[l2++];
} else if (l2 > r2) {
res[index[l1]] += count;
tmp[p++] = index[l1++];
} else if (nums[index[l1]] > nums[index[l2]]) {
tmp[p++] = index[l2++];
count++;
} else {
res[index[l1]] += count;
tmp[p++] = index[l1++];
}
}
for (int i = 0; i < tmp.length; i++) {
index[start+i] = tmp[i];
}
}
}Approach #4 Segment tree
class Solution {
public List<Integer> countSmaller(int[] nums) {
if (nums == null || nums.length == 0) return new ArrayList<>();
int[] minMax = getMinMax(nums);
SegmentTreeNode root = new SegmentTreeNode(minMax[0], minMax[1]);
LinkedList<Integer> ans = new LinkedList<>();
for (int i = nums.length - 1; i >= 0; i--) {
//query
ans.addFirst(query(root, nums[i]));
//update tree;
update(root, nums[i]);
}
return ans;
}
private int query(SegmentTreeNode root, int num) {
if (root == null || root.start >= num) return 0;
if (num > root.end) return root.count;
return query(root.left, num) + query(root.right, num);
}
private void update(SegmentTreeNode root, int num) {
if (num < root.start || num > root.end) return;
root.count++;
if (root.start == root.end) return;
int mid = root.start + (root.end - root.start) / 2;
if (num <= mid) {
if (root.left == null) {
root.left = new SegmentTreeNode(root.start, mid);
}
update(root.left, num);
} else {
if (root.right == null) {
root.right = new SegmentTreeNode(mid + 1, root.end);
}
update(root.right, num);
}
}
private int[] getMinMax(int[] nums) {
int min = nums[0], max = nums[0];
for (int n : nums) {
min = min > n ? n : min;
max = max < n ? n : max;
}
return new int[]{min, max};
}
}
class SegmentTreeNode {
int start;
int end;
int count;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.count = 0;
}
}Approach #5 binary search
public class Solution {
public List<Integer> countSmaller(int[] nums) {
int[] res = new int[nums.length];
List<Integer> list = new ArrayList<>();
for(int i = nums.length - 1; i >= 0; i--) {
res[i] = insert(list, nums[i]);
}
list.clear();
for(int i = 0 ; i < nums.length; i++) {
list.add(res[i]);
}
return list;
}
// binary insert
private int insert(List<Integer> list, int num) {
int l = 0;
int r = list.size() - 1;
while(l <= r) {
int mid = l + (r - l)/2;
int M = list.get(mid);
if(M >= num) {
r = mid - 1;
}else if(M < num) {
l = mid + 1;
}
}
list.add(l, num);
return l;
}
}Last updated