249. Count of Smaller Number before Itself

这道题把,网上太多用SegmentTree做的了,其实不就是一个Insert Sort么

从前往后遍历数组,插入到一个新的数组中。应该插入的index即为其前面比它小的数字的个数。 这个插入的index即是FindInsertPosition那道题几乎一样的即一个Binary Search。 嗯?为啥说几乎?

  1. FindInsertPosition的数字是不重复的。这题里要处理重复的情况。如果找到match直接返回mid是不对的,我们需要找到第一个这个数才可以。所以要在找到数字以后再while下往前找第一个occurence
  2. 第二个错误我费了九牛二虎之力,重新写了一遍再debugger里调试才发现错误。还是处理重复的地方,我之前是这样写的
public int findInsertPosition(ArrayList<Integer> list, int k){
...//other code above
while(mid>0 && list.get(mid)==list.get(mid-1)){ mid--; }
...//other code below
}

那里错了?

ArrayList.get 返回的是一个object。虽然我们用了这么久ArrayList<Integer>但是大多都是直接用的值,甚至 int a = list.get(i) 之类的。都没有意识到返回的是Integer 不是 int 类型。所以不可以用双等号。改用了equals 直接AC

3. 上面那么做之所以费劲的主要原因是我把list.get(mid)=k这个情况但拿出来看而且还要再往前走了。其实如果把问题想成是找第一个大于等于值k的数字来看就好了,所以就是while(left<right){} 里面 if(list[mid]<k), left = mid+1, 小了肯定不要了. else{ right = mid}如果大于等于,就留着right继续缩小范围。这样就可以保证最后剩下的left=right=第一个大于等于k的值的index。

PS,LeetCode 315是问After Itself,这道题是before。唯一区别是遍历数组从后还是从前面开始遍历而已。

Like what you read? Give DeReK a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.