2948. Make Lexicographically Smallest Array by Swapping Elements

trick, use group Sorting index

T: O(nlogn + n*nlogn), worst case
S: O(n)

```java
public class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        List<Integer> indexes = new ArrayList<>();
        List<Integer> values = new ArrayList<>();
        TreeMap<Integer, List<Integer>> map = new TreeMap<>(); // value, list(index)
        for (int i = 0; i < nums.length; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        int[] result = new int[nums.length];
        Integer preKey = null;
        for (int key : map.keySet()) {
            if (preKey != null && key - preKey > limit) { // means new group, add to Result (with sort)
                addResult(result, indexes, values);
            }
            for (int index : map.get(key)) {
                // key - preKey <= limit, so keep adding to this group
                indexes.add(index);
                values.add(key);
            }

            preKey = key;
        }
        addResult(result, indexes, values);

        return result;
    }
    private void addResult(int[] result, List<Integer> indexes, List<Integer> values) {
        Collections.sort(indexes);
        for (int i = 0; i < indexes.size(); i++) {
            result[indexes.get(i)] = values.get(i);
        }
        indexes.clear();
        values.clear();
    }
}
/**
T: O(nlogn + n*nlogn), worst case
S: O(n)

grouping idea:
sort these values first, by TreeMap (values, index)
so values is sorted, so we can loop these sorted values to find cur_value - pre_value <= limit

-> case1: if fit cur_value - pre_value <= limit, means same group
case2: not fit -> means next group, a new group start


so now we continuously add (values, index) to this same group

ex:
index  0  1 2  3  4  5   6  7  8 9
      [1,60,34,84,62,56,39,76,49,38], limit = 4
sorted values:
index:    2   9   6         5   1   4
        |            |    |            |    |
      1,  34, 38, 39,  49,  56, 60, 62,  76 ,  84  

1 is a group,   34 - 1 > limit, so open new group (case2)
34, 38, 39 is a group, because 38 - 34 <= limit, 39 - 38 <= limit (case1)

34, 38, 39 real index is 2   9   6

so if we sort these index [2, 9, 6] to [2, 6, 9]
and put values with same index in values list
index list [2, 6, 9]
value list [34, 38, 39]
            
result become 
index  0  1 2  3  4  5   6       7  8   9
      [1,60,34,84,62,56,39 -> 38,76,49,38 -> 39]
        becomes:
      [1,60,34,84,62,56,38,76,49,39]
       that's what we want!!

       after all grouping and sort index:
       ans is:
      [1,56,34,84,60,62,38,76,49,39]




    x       x  x 
      x            x       x   
[1,60,34,84,62,56,39,76,49,38]

  |            |    |            |    |
1,  34, 38, 39,  49,  56, 60, 62, 76 ,  84 

[0]
[1]

[2]
[34]

[2, 9]
[34, 38]

[2, 9, 6]
[34, 38, 39]


[8]
[49]
[5]
[56]
[5, 1]
[56, 60]
[5, 1, 4]
[56, 60, 62]
[7]
[76]
[3]
[84]



 */

```