My code:
import java.util.Arrays;
import java.util.List;
public class Solution {
class Node {
int val = 0;
int sum = 0;
int dup = 0;
Node left;
Node right;
Node(int val, int sum) {
this.val = val;
this.sum = sum;
this.dup = 1;
}
}
public List<Integer> countSmaller(int[] nums) {
Node root = null;
Integer[] arr = new Integer[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
root = helper(root, nums[i], i, arr, 0);
}
return Arrays.asList(arr);
}
private Node helper(Node root, int num, int i, Integer[] arr, int preSum) {
if (root == null) {
root = new Node(num, 0);
arr[i] = preSum;
}
else if (root.val == num) {
root.dup++;
arr[i] = preSum + root.sum;
}
else if (root.val < num) {
root.right = helper(root.right, num, i, arr, preSum + root.sum + root.dup);
}
else {
root.sum += 1;
root.left = helper(root.left, num, i, arr, preSum);
}
return root;
}
}
reference:
https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst/2
这道题目的这个解法，还是很难理解的。花了挺长一段时间去理解。
做难题真的花时间，今天的效率也真够低的。
他通过建立一个 类似于BST的树，来解决这个问题。
sum 存的是，当前结点所表示的value，和当前访问处的value，这段范围内，小于当前结点value的个数。
比较绕。
preSum 表示的是，当前结点表示的value，在该value右侧，比他小的个数
比如：
[3, 2, 1, 2, 6, 1]
1(0, 1) sum = 0, dup = 1
=>
1(0, 1)
\ preSum = 0 + 0 + 1
6(0, 1)
=>
1(0, 1)
\ preSum = 0 + 0 + 1
6(1, 1) dup++
/ preSum = 1
2(0, 1)
=>
1(0, 2) dup++
6(1, 1)
/
2(0, 1)
=>
1(0, 2)
6(1, 1)
/
2(0, 2) dup++
preSum = preSum + root.sum
=>
1(0, 2)
6(1, 1)
/
2(0, 2)
3(0, 1)
还是不太好理解的。
Solution2:
My code:
public class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
Integer[] ret = new Integer[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
int index = findIndex(list, nums[i]);
ret[i] = index;
list.add(index, nums[i]);
}
return Arrays.asList(ret);
}
private int findIndex(List<Integer> ret, int target) {
if (ret.size() == 0) {
return 0;
}
int begin = 0;
int end = ret.size() - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (ret.get(mid) > target) {
end = mid - 1;
}
else if (ret.get(mid) < target) {
begin = mid + 1;
}
else {
while (mid - 1 >= 0 && ret.get(mid - 1).equals(ret.get(mid))) {
mid--;
}
return mid;
}
}
return begin;
}
}
reference:
https://discuss.leetcode.com/topic/31173/my-simple-ac-java-binary-search-code/2
这个时间复杂度很大。
注意， Integer 比较，用 .equals() !!!!!
还有一种 Merge sort的写法，以后再理解吧。
Anyway, Good luck, Richardo! -- 10/08/2016
My code:
public class Solution {
int[] count;
int[] index;
public List<Integer> countSmaller(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return ret;
}
int len = nums.length;
count = new int[len];
index = new int[len];
for (int i = 0; i < len; i++) {
index[i] = i;
}
mergesort(nums, 0, len - 1);
for (int i = 0; i < count.length; i++) {
ret.add(count[i]);
}
return ret;
}
private void mergesort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergesort(nums, start, mid);
mergesort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
private void merge(int[] nums, int start, int mid, int end) {
int[] arr = new int[end - start + 1];
for (int i = start; i <= end; i++) {
arr[i - start] = nums[i];
}
int[] temp = new int[end - start + 1];
for (int i = start; i <= end; i++) {
temp[i - start] = index[i];
}
int p = start;
int p1 = start;
int p2 = mid + 1;
int cnt = 0;
while (p1 <= mid && p2 <= end) {
if (arr[p1 - start] > arr[p2 - start]) {
cnt++;
index[p] = temp[p2 - start];
nums[p] = arr[p2 - start];
p++;
p2++;
}
else {
index[p] = temp[p1 - start];
nums[p] = arr[p1- start];
count[index[p]] += cnt;
p++;
p1++;
}
}
while (p2 <= end) {
index[p] = temp[p2 - start];
nums[p] = arr[p2 - start];
p++;
p2++;
}
while (p1 <= mid) {
index[p] = temp[p1 - start];
nums[p] = arr[p1 - start];
count[index[p]] += cnt;
p++;
p1++;
}
}
}
这是一种新的办法，并且可以保证时间复杂度是 O(nlogn)
上面的BST方法，在最坏情况下复杂度是 O(n^2)
这个 merge sort 方法其实挺难理解的。问了同学才略懂。
当我们merge 到一层时，假设有左右两个部分，left and right
left is sorted and right is sorted
然后我们 merge 的时候，
right部分的所有元素， 他们的 count of smaller numbers 一定是 0!
我们要关注的是左部分。 left part
如果 left[p1] < right[p2]
按照以往的merge sort经验，我们有一个arrray来放merge过后的新数组。
nums[p] = left[p1]
p++;
p1++;
if left[p1] > right[p2]
nums[p] = right[p2];
p++;
p2++;
这里要注意了，我们需要记录的，是右侧比左侧小的个数。
所以我们有一个变量 cnt
当 left[p1] > right[p2]
我们需要把right[p2] 移动到 left[p1] 的左侧，记住，这个时候，
对于 left[p1, mid],他们的 count of smaller numbers 至少有了1，即,这个 right[p2]
同时，因为merge sort, 原有的顺序都被打乱了。我们需要记录下，新merge过的数组，他们的元素，在原数组中的index
这样，当我们发现右边比左边小时，cnt++
当我们发现左边比右边小时，就可以更新 count 了
对应的index 就是 index[p]
差不多理解下把。
Anyway, Good luck, Richardo! -- 10/09/2016
