优化一段代码，主要是for循环。希望减少运行时间。

Question

下面这段代码是将输入的数字进行排序后，将排好的序号替换掉原来数组中元素位置上的值。

例如

求优化下列代码。运行时间长，效率不高。

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int i, j, k;
       
        int arr_a[] = arr;
        HashSet<Integer> set = new HashSet<>();

//        for (int i1 : arr_a) {
//            System.out.println(i1);
//
//        }

        for (int x = 0; x < arr.length; x++) {
            set.add(arr_a[x]);
        }
        Integer arr_b[] = set.toArray(set.toArray(new Integer[]{}));

        for (i = 0; i < arr_b.length - 1; i++) {
            for (j = 0; j < arr_b.length - i - 1; j++) {
                if (arr_b[j] > arr_b[j + 1]) {
                    k = arr_b[j];
                    arr_b[j] = arr_b[j + 1];
                    arr_b[j + 1] = k;
                }
            }

        }
       
        for (int i1 = 0; i1 < arr.length; i1++) {
            for (int i2 = 0; i2 < arr_b.length; i2++) {
                if (arr[i1] == arr_b[i2]) {
                    arr[i1] = i2 + 1;
                    break;

                }

            }


        }
        return arr;

    }
}

Answer 1

你的算法慢是因为：

1. 你用的排序算法是O(n^2), 可以直接用Arrays.sort()优化。
2. 你最后获取序号的算法也是O(n^2), 可以用哈希表优化成O(n)

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] arr_copy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(arr_copy);
        Map<Integer, Integer> record = new HashMap<>();
        int index = 1;
        for (int num : arr_copy) {
            if (!record.containsKey(num)) {
                record.put(num, index++);
            }
        }
        for (int i=0; i<arr.length; ++i) {
            arr[i] = record.get(arr[i]);
        }
        return arr;
    }
}