力扣刷题之数组序号计算（每日一题7/28）

力扣刷题之数组序号计算（每日一题7/28） 题目如下

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。 序号代表了一个元素有多大。序号编号的规则如下： 序号从 1 开始编号。 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。 每个数字的序号都应该尽可能地小。

力扣 链接

最后它给了一点提示

这个数据量是绝对会测试你的程序的算法执行效率的。单纯的用for循环做的话，不太行。下面给出自己之前一些愚蠢的尝试。下面这个也是可以去计算出来的，但是在大量数据面前就执行效率很慢，原因是for循环的过多使用。

 class Solution {
        public int[] arrayRankTransform(int[] arr) {
            int i, j, k;

            int arr_a[] = arr;
            HashSet 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[] = (Integer[]) 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;

        }
    }

复制

可笑的是，我明明都已经开始用集合了，后来又去用for循环了。

下面给出优化后的解题方法。我用了一个HashMap的数据结构。这个数据结构是双列数据结构。并且不会允许键重复，并且是散列的具有无序的特点。不过这个无所谓，我用这个数据结构的目的就是为了存储排序后的数组的值。来看具体怎么体现。 自己定义了数组进行的测试，在力扣提交的时候只需要将自己定义的重复的数组删掉，最后要返回一个最终的数组。

如下，首先对当前数组进行了排序，这个默认是从何小到大排序的，题目实际的要求也是这样，所以不用修改默认。

排序后的数组中的元素一定是按照顺序排列的，是从小到大排序的。

思路：用HashMap数据结构存储数组排序后的值，作为集合的键，集合的值可以自然增长。因为我们数组排序后是按从小到大排序，那么我们这样把它的从小到大的值对应到从小到大的索引值+1。其实可以让键对应的值从1开始变大就可以。因为我们最后排序的时候也是要1开始计算的。

class Solution {
    public int[] arrayRankTransform(int[] arr) {
         int[] arr_new = Arrays.copyOf(arr, arr.length);

        Arrays.sort(arr);

        HashMap<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < array.length; i++) {
//            if(!map.containsKey(array[i]))
//            {
//                map.put(array[i],i+1);
//            }
//        }
//
        for (int i : arr) {
        //要保证不要存储重复的键，当然map本身也不允许重复，
        //只是你如果进行存储重复的键的话，值得话会被覆盖。
         //这样的话后面的排序就乱套了。题目要求的，如果两个数字一样的话，
        //他们的最终替代的值也是一样的。所以我们只保留可能
        //出现同样数字的一个值
            if (!map.containsKey(i))
            {
                map.put(i,map.size()+1);
            }
        }
        //下面我们进行一个重新的赋值，将排序替换掉原来的数字。
        for (int i = 0; i < arr.length; i++) {
            arr_new[i]= map.get(arr_new[i]);
        }
        return arr_new;
    }
}      

复制

想想其中一段你会这样去写吗？这样写是不对的。如果出现相同的数，它其实是不要存储的，但是你的按照这个索引i还是会变大，这样是不对的。

 for (int i = 0; i < array.length; i++) {
            if(!map.containsKey(array[i]))
            {
                map.put(array[i],i+1);
            }
        }

复制

要用普通的for的话还是得这样写

         for (int i = 0; i < arr.length; i++) {
            if(!map.containsKey(arr[i]))
            {
                map.put(arr[i],map.size()+1);
            }
        }

复制

需要注意的是数组的拷贝，你会不会这样写？ 这样写的话也可以获取到和原来数组一样的元素存储，但是如果你将来对摸一个数组排序的话，拎一个数组也会跟着变。因为这样的其实是一个指针的指向，指向原来数组的地址，当然一个数组变，另一个也会变。

这样你重新赋值的话就赋给位置不是原来的数了。

 int[] arr_new = arr;

复制

这是需要注意的地方。用hash集合操作的话其实还是效率比较高的。

基本上这个体无论怎么操作道理都是一样的。