1331.rank-transform-of-an-array.md

1331. 数组序号转换

TreeSet + HashMap

• TreeSet 去重 + 排序

代码实现

class Solution {
    public int[] arrayRankTransform(int[] w) {
        TreeSet<Integer> st = new TreeSet<>();
        for (int i: w) st.add(i);

        Iterator<Integer> it = st.iterator();
        int cnt = 0;

        Map<Integer, Integer> map = new HashMap<>();
        while (it.hasNext()){
            map.put(it.next(), ++cnt);
        }

        int n = w.length;
        int res[] = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = map.get(w[i]);
        }

        return  res;
    }
}

二分思路

1. 先将原数组排序 $O(NlogN)$
2. 对于每一个元素，二分找到其下标 $O(logN)$；注意，这里的重复元素的下一个元素 下标不会越过，比如 有两个相同元素下标都为 2，下一个更大的元素下标为 3 而不是 4

代码实现

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;

        int raw[] = Arrays.copyOf(arr, n);
        Arrays.sort(arr);
        // 去重
        int cnt = 0;
        for (int i = 0; i< n; i++){
            if (cnt > 0 && arr[cnt-1] == arr[i]) continue;
            arr[cnt++] = arr[i];
        }

        int res[] = new int[n];
        for (int i =0; i < n; i++){
            int l = 0, r = cnt;
            while (l < r){
                int mid = (l+r) >> 1;
                if (arr[mid] >= raw[i]) r=mid;
                else l = mid+1;
            }
            res[i] = l + 1;
        }
        return res;
    }
}