Calculation of array serial number of force deduction questions (daily question 7/28)

Give you an array of integers arr , Please replace each element in the array with their ordinal number after sorting .
The serial number represents how big an element is . The rules for serial numbers are as follows ：
The serial number from 1 Numbered starting .
The bigger an element is , So the bigger the serial number . If two elements are equal , So they have the same serial number .
The serial number of each number should be as small as possible .

Power button
link

Finally, it gives a hint

This amount of data will definitely test the algorithm execution efficiency of your program . Simply use for If you do it circularly , Not very good . Here are some of my previous stupid attempts . The following one can also be calculated , But in front of a large amount of data, the execution efficiency is very slow , as a result of for Excessive use of recycling .

 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;

        }
    }

The irony is , I've already started using collections , Later I used it for Circulated .

Here is the optimized solution . I used one HashMap Data structure of . This data structure is a double column data structure . And will not allow key repetition , And it is hashed and has the characteristics of disorder . But it doesn't matter , The purpose of using this data structure is to store the values of the sorted array . Let's see how to reflect .
I have defined the test of array , When submitting the force deduction, you only need to delete the repeated array defined by yourself , Finally, we need to return a final array .

as follows , First, sort the current array , The default order is from small to large , The actual requirements of the topic are the same , So there is no need to modify the default .

The elements in the sorted array must be arranged in order , It's sorted from small to large .

Ideas ： use HashMap The data structure stores the sorted values of the array , As the key of the set , The value of a set can grow naturally . Because our array is sorted from small to large , So let's map its value from small to large to the index value from small to large +1. In fact, the corresponding value of the key can be changed from 1 Just start getting bigger . Because we also need to 1 Start calculated .

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) {
    
        // Be sure not to store duplicate keys , Of course map It is not allowed to repeat itself ,
        // It's just that if you store duplicate keys , Worthy words will be covered .
         // In this case, the subsequent sorting will be disordered . The title requires , If the two numbers are the same ,
        // Their final substitution value is the same . So we only keep the possibility 
        // A value with the same number appears 
            if (!map.containsKey(i))
            {
    
                map.put(i,map.size()+1);
            }
        }
        // Now let's make a new assignment , Replace the sorting with the original number .
        for (int i = 0; i < arr.length; i++) {
    
            arr_new[i]= map.get(arr_new[i]);
        }
        return arr_new;
    }
}      

Think about one paragraph. Would you write like this ？ It's not right to write like this . If the same number appears , It is actually not stored , But your index i It will still get bigger , It's not right .

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

Use ordinary for You still have to write like this

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

Note the copy of the array , Would you write like this ？
In this way, you can also get the same element storage as the original array , But if you sort an array in the future , Carrying an array will also change . Because this is actually the point of a pointer , Point to the address of the original array , Of course, an array becomes , The other one will change .

In this way, if you re assign a value, you will assign a position other than the original number .

 int[] arr_new = arr;

This is what needs attention . use hash In fact, the efficiency of collection operation is relatively high .

Basically, the principle of this body is the same no matter how it is operated .