Leetcode 315 Count of Smaller Numbers After Self 离散化

这一题可以用Binary Indexed Tree或者Segment Tree做
有两种方法去建树：
1） 算出数组元素最大最小值，根据权值值域建树
2） 将数组元素离散化，值转换成rank，根据rank （数组大小）建树，最优解

但是在2） 中，离散化这一步是这样实现的：

1. private void discretization(int[] nums) {
   
2.         int[] sorted = nums.clone();
   
3.         Arrays.sort(sorted);
   
4.         for (int i = 0; i < nums.length; i++) {
   
5.             nums[i] = Arrays.binarySearch(sorted, nums[i]) + 1;
   
6.         }
   
7.     }

复制代码

如果nums[i]有duplicate values的情况下，根据documentation：If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
https://docs.oracle.com/javase/7 ... s.html#binarySearch(byte[],%20byte)
那么相同value的nums[i]可能会return不同的rank，这样算出来的count有可能会不对？可是我按照这个方式去离散化，提交是可以通过的，请问有小伙伴可以解释一下么？


以下是第一种和第二种方法的完整代码
1） 最大最小值

1. class Solution {
   
2.     public List<Integer> countSmaller(int[] nums) {
   
3.         // write your code here
   
4.         List<Integer> list = new LinkedList<Integer>();
   
5.         int min = Integer.MAX_VALUE;
   
6.         int max = Integer.MIN_VALUE;
   
7.         for (int i = 0; i < nums.length; i++) {
   
8.             min = Math.min(min, nums[i]);
   
9.             max = Math.max(max, nums[i]);
   
10.             list.add(0);
    
11.         }
    
12.         int[] c = new int[max - min + 2];
    
13.         for (int i = nums.length - 1; i >= 0; i--) {
    
14.             int val = sum(nums[i] - 1 - min, c);
    
15.             update(nums[i] - min, 1, c);
    
16.             list.set(i, val);
    
17.         }
    
18.         return list;
    
19.     }
    
20.     private int lowbit(int x) {
    
21.         return x & -x;
    
22.     }
    
23.     private void update(int index, int val, int[] c) {
    
24.         index++;
    
25.         for (int i = index; i <= c.length - 1; i += lowbit(i)) {
    
26.             c[i] += val;
    
27.         }
    
28.     }
    
29.     private int sum(int index, int[] c) {
    
30.         index++;
    
31.         int res = 0;
    
32.         for (int i = index; i > 0; i -= lowbit(i)) {
    
33.             res += c[i];
    
34.         }
    
35.         return res;
    
36.     }
    
37. }

复制代码

2) 离散化之后

1. class Solution {
   
2.     public List<Integer> countSmaller(int[] nums) {
   
3.         // write your code here
   
4.         List<Integer> list = new LinkedList<Integer>();
   
5.         for (int i = 0; i < nums.length; i++) {
   
6.             list.add(0);
   
7.         }
   
8.         discretization(nums);
   
9.         int[] c = new int[nums.length + 1];
   
10.         for (int i = nums.length - 1; i >= 0; i--) {
    
11.             int val = sum(nums[i] - 1, c);
    
12.             update(nums[i], 1, c);
    
13.             list.set(i, val);
    
14.         }
    
15.         return list;
    
16.     }
    
17.     private void discretization(int[] nums) {
    
18.         int[] sorted = nums.clone();
    
19.         Arrays.sort(sorted);
    
20.         for (int i = 0; i < nums.length; i++) {
    
21.             nums[i] = Arrays.binarySearch(sorted, nums[i]) + 1;
    
22.         }
    
23.     }
    
24.     private int lowbit(int x) {
    
25.         return x & -x;
    
26.     }
    
27.     private void update(int index, int val, int[] c) {
    
28.         index++;
    
29.         for (int i = index; i <= c.length - 1; i += lowbit(i)) {
    
30.             c[i] += val;
    
31.         }
    
32.     }
    
33.     private int sum(int index, int[] c) {
    
34.         index++;
    
35.         int res = 0;
    
36.         for (int i = index; i > 0; i -= lowbit(i)) {
    
37.             res += c[i];
    
38.         }
    
39.         return res;
    
40.     }
    
41. }

复制代码

找到值不一定主要是针对首尾说的. 因为源代码里面写只要nums[m] == target 就返回了

这个里面首尾固定, 找出来是一样的.

补充内容 (2018-7-11 05:28):
举个极端点的例子, [10,1,1,1,1,1,1,1,1,1] 这样你nums[i] 会变成[10, 5,5,5,5,5,5,5,5,5] 但是这个rank是不影响你fenwick树里面找frequency, 因为比5小的rank是0个.

肥宅快乐水 发表于 2018-7-11 05:19
找到值不一定主要是针对首尾说的. 因为源代码里面写只要nums[m] == target 就返回了

这个里面首尾固定,  ...

[10,1,1,1,1,1,1,1,1,1] 有可能会变成［10，1，2，3，4，5，6，7，8，9］，因为只要找到1就返回它的index，然后加一作为rank，而这里有多个1，无法确定返回的是哪一个呀？

jocelyna 发表于 2018-7-11 06:46
[10,1,1,1,1,1,1,1,1,1] 有可能会变成［10，1，2，3，4，5，6，7，8，9］，因为只要找到1就返回它的index ...

可是真的不会。

你看binarySearch 代码呗。。你说会不会变成【10，1，2，3，4，5，6，7，8，9】

```
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }

    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
```

肥宅快乐水 发表于 2018-7-11 10:47
可是真的不会。

你看binarySearch 代码呗。。你说会不会变成【10，1，2，3，4，5，6，7，8，9】

嗯嗯，确实是的，那就是首尾的index确定的情况下，return回来的index应该是一样的，即使是有重复元素

jocelyna 发表于 2018-7-11 11:42
嗯嗯，确实是的，那就是首尾的index确定的情况下，return回来的index应该是一样的，即使是有重复元素

我回头又想了一下， 这个题我还是建议用merge sort做。
- 方便， - 好写， -容易变形

bit这个方法我想了一下，似乎应用不到别的题上面， 而且需要preprocess，也不是说不好，单纯觉得应用很窄。