三刷 07/2022
Version #4 Merge Sort
这个思路不看答案是完全想不到的，但是速度很快
For each element i, the function records the number of elements jumping from i's right to i's left during the merge sort.
当merge的时候如果left element小于right element，此时要放置left，那么所有在这个left之前放下去的right都是比它小且在它右边的
Time O(NlogN)
Space O(N)
Runtime: 58 ms, faster than 93.73% of Java online submissions for Count of Smaller Numbers After Self.
Memory Usage: 61.1 MB, less than 88.66% of Java online submissions for Count of Smaller Numbers After Self.
class Solution {
public List<Integer> countSmaller(int[] nums) {
// merge sort the indices
int[] indices = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
indices[i] = i;
}
int[] count = new int[nums.length];
sort(nums, indices, count, 0, nums.length - 1, new int[nums.length]);
List<Integer> result = new ArrayList<>();
for (int cnt : count) {
result.add(cnt);
}
return result;
}
private void sort(int[] nums, int[] indices, int[] count, int start, int end, int[] aux) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
sort(nums, indices, count, start, mid, aux);
sort(nums, indices, count, mid + 1, end, aux);
merge(nums, indices, count, start, end, aux);
}
private void merge(int[] nums, int[] indices, int[] count, int start, int end, int[] aux) {
for (int i = start; i <= end; i++) {
aux[i] = indices[i];
}
int mid = start + (end - start) / 2;
int left = start, right = mid + 1;
int p = start;
// m+1 r
// 1 4 5 2 6 8
// 1 2 4
while (left <= mid && right <= end) {
if (nums[aux[left]] <= nums[aux[right]]) {
indices[p] = aux[left];
count[indices[p]] += right - (mid + 1);
left++;
} else {
indices[p] = aux[right];
right++;
}
p++;
}
while (left <= mid) {
indices[p] = aux[left];
count[indices[p]] += right - (mid + 1);
left++;
p++;
}
while (right <= end) {
indices[p] = aux[right];
right++;
p++;
}
}
}
Version #3 Segment Tree
Time O(Nlog(max - min))
Space O(2(max - min))
Runtime: 248 ms, faster than 39.95% of Java online submissions for Count of Smaller Numbers After Self.
Memory Usage: 131 MB, less than 55.08% of Java online submissions for Count of Smaller Numbers After Self.
class Solution {
class Node {
int start, end;
int count;
Node left, right;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
}
public List<Integer> countSmaller(int[] nums) {
int min = (int)(1e4);
int max = -(int)(1e4);
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
Node root = buildTree(min, max);
List<Integer> result = new LinkedList<>();
for (int i = nums.length - 1; i >= 0; i--) {
result.add(0, query(nums[i], root));
update(nums[i], root);
}
return result;
}
private int query(int num, Node root) {
if (root.start == root.end) {
if (root.start < num) {
return root.count;
}
return 0;
}
// [start, mid] [mid + 1, end]
// count of numbers smaller than num
int mid = root.start + (root.end - root.start) / 2;
if (num <= mid) {
return query(num, root.left);
}
return root.left.count + query(num, root.right);
}
private void update(int num, Node root) {
if (root.start == num && root.end == num) {
root.count++;
return;
}
int mid = root.start + (root.end - root.start) / 2;
if (num <= mid) {
update(num, root.left);
} else {
update(num, root.right);
}
root.count = root.left.count + root.right.count;
}
private Node buildTree(int start, int end) {
if (start == end) {
return new Node(start, start);
}
Node root = new Node(start, end);
int mid = start + (end - start) / 2;
root.left = buildTree(start, mid);
root.right = buildTree(mid + 1, end);
return root;
}
}
二刷
Version #2 Prefered BIT
有两个非常非常重要的点
第一个index 必须start from 1，否则在 i += (i & (-i))上就会进入死循环
第二个就是因为有负数，所以不能直接用nums[i]来表示index
discuss里面的做法是给所有的数都加一个offset，看了一个更好的做法就是sort以后给所有的数一个rank，然后用这个rank作为index，这样也避免了
[1, 1000]这种数据浪费空间的问题，非常厉害了
时间复杂度
initial sort O(nlogn)
iterate throught nums(n) and update(logn) and query(logn) -> O(nlogn)
所以total Time O(nlogn)
Space O(# nums)
50.74 %
class Solution {
private int[] tree;
private int[] count;
public List<Integer> countSmaller(int[] nums) {
// use num as index, count as value
TreeSet<Integer> treeSet = new TreeSet<>();
for (int num : nums) {
treeSet.add(num);
}
int rank = 1;
// map num value to its rank
Map<Integer, Integer> map = new HashMap<>();
Iterator<Integer> iter = treeSet.iterator();
while (iter.hasNext()) {
int num = iter.next();
map.put(num, rank);
rank++;
}
// rank equals to last rank + 1
List<Integer> result = new ArrayList<>();
tree = new int[rank];
count = new int[rank];
for (int i = nums.length - 1; i >= 0; i--) {
int rankIndex = map.get(nums[i]);
count[rankIndex]++;
updateTree(rankIndex, 1);
result.add(query(rankIndex - 1));
}
Collections.reverse(result);
return result;
}
private void updateTree(int i, int val) {
while (i < tree.length) {
tree[i] += val;
i += (i & (-i));
}
}
private int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= (i & (-i));
}
return sum;
}
}
Version #1 Self-defined BST
写了 insert 函数，哈哈
Every insertion O(height) -> O(logn) ~ O(n)
n times insertion
Total O(nlogn) ~ O(n^2)
86.26 %
class Solution {
private class TreeNode {
int leftCount;
int currCount;
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
currCount = 1;
}
}
public List<Integer> countSmaller(int[] nums) {
// Insert a node
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
TreeNode root = new TreeNode(nums[nums.length - 1]);
result.add(0);
for (int i = nums.length - 2; i >= 0; i--) {
int count = insertNode(root, nums[i]);
result.add(count);
}
Collections.reverse(result);
return result;
}
private int insertNode(TreeNode root, int val) {
TreeNode curr = root;
int count = 0;
while (curr != null) {
if (val == curr.val) {
curr.currCount++;
count += curr.leftCount;
break;
} else if (val < curr.val) {
curr.leftCount++;
if (curr.left != null) {
curr = curr.left;
} else {
curr.left = new TreeNode(val);
break;
}
} else { // val > curr.val
count += curr.leftCount + curr.currCount;
if (curr.right != null) {
curr = curr.right;
} else {
curr.right = new TreeNode(val);
break;
}
}
}
return count;
}
}
一刷
应该改进一下写一个Insert函数
66.11 %
/* TreeNode int val, selfCount, leftCount
/ \
left right
*/
class TreeNode {
public int selfCount;
public int leftCount;
public TreeNode left, right;
public int val;
public TreeNode(int val) {
this.val = val;
selfCount = 1;
leftCount = 0;
}
}
public class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
TreeNode root = new TreeNode(nums[nums.length - 1]);
result.add(0);
TreeNode curr = null;
int pathCount = 0;
for (int i = nums.length - 2; i >= 0; i--) {
curr = root;
pathCount = 0;
int value = nums[i];
while (curr != null) {
if (curr.val == value) {
pathCount += curr.leftCount;
curr.selfCount++;
break;
// go right
} else if (value > curr.val) {
pathCount += curr.selfCount + curr.leftCount;
if (curr.right == null) {
curr.right = new TreeNode(value);
curr = curr.right;
}
curr = curr.right;
// go left
} else {
curr.leftCount++;
if (curr.left == null) {
curr.left = new TreeNode(value);
curr = curr.left;
}
curr = curr.left;
}
}
result.add(pathCount);
}
Collections.reverse(result);
return result;
}
}
No comments:
Post a Comment