315. Count of Smaller Numbers After Self
写了好几遍。。。这个题还是需要重新做 主要问题在于 怎么把原来的计算结果叠加到现有的上面 以及怎么处理相同的元素
改变原来的数据结构 每个节点存取比自己小的节点个数 和与自己值相同的个数 一边建树一边计算比自己小的个数 用cnt表示
Time Analysis: 插入节点O(logN) 外层循环N 一共是O(NlogN) 但是worst case....如果形成的Tree不是balanced 则是N方的复杂度
public class Solution {
/** @smaller: the number of nodes smaller than this node
* @count: the number of duplicate nodes
* */
public class TreeNode{
TreeNode left;
TreeNode right;
int val;
int count;
int smaller;
public TreeNode(int val){
this.count = 1;
this.val = val;
this.smaller = 0;
}
}
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if(nums == null||nums.length == 0)return res;
int n = nums.length;
TreeNode root = new TreeNode(nums[n - 1]);
res.add(0,0);
//insert each node into the "tree" traverse from the end --> start of array
for(int i = n - 2;i >= 0;i--){
res.add(insert(root,nums[i]));
}
Collections.reverse(res);
return res;
}
public int insert(TreeNode root,int val)
{
int cnt = 0;
//if the current value is smaller than the root node we need to continue traversing down to the left
while(root != null){
if(val < root.val){
root.smaller++;
if(root.left == null){
root.left = new TreeNode(val);
break;
}
root = root.left;
}
//if the current value is larger we need to add the root's own count to the current count value and
else if(val > root.val){
cnt = cnt + root.smaller + root.count;
if(root.right == null){
root.right = new TreeNode(val);
break;
}
root = root.right;
}
//update the count value and copy the value of the duplicate one(一样的数肯定有相同数目比自己小的)
else{
cnt += root.smaller;
root.count++;
break;
}
}
return cnt;
}
}
220. Contains Duplicate III
Utilize Subset of treeset to see whether there are enough gaps by going the positive direction and negative direction.
同样的维护一个window 当window size大于K的时候 移走最左边的元素
"The subSet(E fromElement,E toElement) method is used to return a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive."
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int len = nums.length;
if(nums == null || len < 2|| k < 0 || t < 0){
return false;
}
TreeSet<Long> set = new TreeSet<Long>();
for(int i = 0;i < len;i++){
long value = (long)nums[i];
//正负两个方向
SortedSet<Long> sort = set.subSet(value - t,value + t + 1);
if(sort.size() > 0){
return true;
}
set.add(value);
set.remove((long)nums[i - k]);
}
}
return false;
}
}
327. Count of Range Sum
这个题让我们返回所有的(i , j)index数对个数使得[i ,j]之间的range sum再一个给定的区间范围内。首先可以肯定的是
这个题可以用BruteForce做 但是很慢需要优化
（1）分治
计算出Prefix数组 然后分治的看待问题 两个指针可能都是在数组左边 也可能都是在数组右边 也有可能是一个在左边
一个在右边。 而在计算第三种情况的时候 最好的情况下是两个分数组都是Sorted 这样我们计算了一个range里的指针j 在下一个
指针i移动的时候不用重新开始（因为rangesum = sum(j) - sum(i) 而sum(i)部分是递增的。同时为了Sort数组 我们也要进行merge
sort里面的merge操作
Merge有两种写法 一个就是以前经常用到的 两个指针比较 移动赋值 然后再处理剩余的元素 还有一个就是这道题里用的
public class Solution {
/** Divide and Conquer: Using Merge Sort **/
public int countRangeSum(int[] nums, int lower, int upper) {
//build the sum[j] array of elements from 0 until j+1
int len = nums.length;
long[] sum = new long[len + 1];
for(int i = 0;i < len;i++){
sum[i + 1] = sum[i] + nums[i];
}
return helperCount(sum,lower,upper,0,len + 1);
}
public int helperCount(long[] sums,int lower,int upper,int start,int end){
if(end <= start + 1)return 0;
//divide
int mid = start + (end - start)/2;
int count = helperCount(sums,lower,upper,start,mid)+helperCount(sums,lower,upper,mid,end);
long[] temp = new long[end - start];
int k = mid;
int j = mid;
int s2 = mid;
for(int i = start,idx = 0;i < mid;i++,idx++){
//Merge
while(s2 < end && sums[s2] < sums[i]) temp[idx++] = sums[s2++];
//count
while (k < end && sums[k] - sums[i] < lower) k++;
while (j < end && sums[j] - sums[i] <= upper) j++;
temp[idx] = sums[i];
count += j - k;
}
System.arraycopy(temp, 0, sums, start, s2 - start);
return count;
}
}
2.有一个很好的写的总结用index tree的解法 继续参考 。。目前无法做到想起来用这个数据结构