2. Linux.do
  3. Leetcode每日一题 —— 2948. 交换得到字典序最小的数组

Leetcode每日一题 —— 2948. 交换得到字典序最小的数组

魔法师 2026-08-29 08:59 1


思路


一个很朴素的想法，先把nums克隆后排序，遍历一遍通过与前一个值的差就知道哪些数值可以交换。把可以互相交换的值加到数组里，把hash的值指向数组指针。

然后遍历原nums数组，从当前值对应的数组中找出没用过的第一个元素放到该位置。

nums数组就是最终需要的答案


代码


class Solution {

    public int[] lexicographicallySmallestArray(int[] nums, int limit) {

        HashMap<Integer, List<Integer>> map = new HashMap<>();

        int[] sorted = nums.clone();

        Arrays.sort(sorted);

        int last = Integer.MIN_VALUE >> 1;

        List<Integer> list = null;

        for (int num : sorted) {

            if (num - last > limit) {

                list = new ArrayList<>();

                list.add(1);

            }

            list.add(num);

            last = num;

            map.put(num, list);

        }

        for (int i = 0; i < nums.length; i++) {

            int num = nums[i];

            list = map.get(num);

            nums[i] = list.get(list.getFirst());

            list.set(0, list.getFirst() + 1);

        }

        return nums;

    }

}
最新回复 (2)
  • Lvvvv 08-29 10:37
    1楼

    写了一坨构式，神了。


    class Solution {
    
public:
    
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
    
        int n = nums.size();
    
        vector<int> p(n,0);
    
        iota(p.begin(),p.end(),0);
    
        auto find = [&](this auto&& find, int x) -> int {
    
            return p[x] == x ? x : p[x] = find(p[x]);
    
        };
    
        vector<pair<int,int>> nums_with_id(n);
    
        for(int i = 0; i < n; i++) {
    
            nums_with_id[i] = make_pair(nums[i],i);
    
        }
    
        sort(nums_with_id.begin(),nums_with_id.end());
    
        for(int i = 0; i + 1 < n; i++) {
    
            int va = nums_with_id[i].first, vb = nums_with_id[i + 1].first;
    
            if(vb - va <= limit) {
    
                int ida = nums_with_id[i].second, idb = nums_with_id[i + 1].second;
    
                int pa = find(ida), pb = find(idb);
    
                if(pa != pb) {
    
                    p[pa] = pb;
    
                }
    
            }
    
        }
    
        vector<vector<int>> seq_id(n,vector<int>()), seq_val(n,vector<int>());
    
        for(int i = 0; i < n; i++) {
    
            int pi = find(i);
    
            seq_id[pi].push_back(i);
    
            seq_val[pi].push_back(nums[i]);
    
        }
    
        for(int i = 0; i < n; i++) {
    
            sort(seq_id[i].begin(),seq_id[i].end());
    
            sort(seq_val[i].begin(),seq_val[i].end());
    
        }
    
        vector<int> res(n);
    
        for(int i = 0; i < n; i++) {
    
            for(int j = 0; j < seq_id[i].size(); j++) {
    
                res[seq_id[i][j]] = seq_val[i][j];
    
            }
    
        }
    
        return res;
    
        
    
    }
    
};
  • SomeBottle 08-29 11:03
    2楼

    写起来感觉很有点绕，排序，分组然后再排序。


    class Solution {
    
public:
    
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
    
        // 都是正整数
    
        // 且只要两数之差 <= limit 就可以交换
    
        // 对于每个数字我们需要看后面有没有更小且满足交换要求的
    
        // 输入规模可能较大，需要预处理
    

    
        // 先按值排序，但为了后续交换，还得保留下标
    
        vector<pair<int,int>> nps;
    
        for(int i=0;i<nums.size();i++){
    
            nps.emplace_back(nums[i],i);
    
        }
    
        sort(nps.begin(),nps.end());
    
        // 接下来可以分组了，相邻值 <= limit 的全都可以互相交换，算作一组
    
        vector<vector<int>> idxs; // 存每一组的下标
    
        int prevVal=-limit;
    
        for(auto& p:nps){
    
            if(p.first-prevVal>limit){
    
                // 超出限制，新分组出现
    
                idxs.emplace_back();
    
            }
    
            idxs.back().emplace_back(p.second);
    
            prevVal=p.first;
    
        }
    
        // 对每个组分别进行排序
    
        for(auto& g:idxs){
    
            // 按下标排序
    
            sort(g.begin(),g.end());
    

    
            // 取出这一组的值
    
            vector<int> vals;
    
            for(int idx:g){
    
                vals.emplace_back(nums[idx]);
    
            }
    
            // 再排序 vals
    
            sort(vals.begin(),vals.end());
    
            // 较小值分配给较小下标
    

    
            for(int i=0;i<g.size();i++){
    
                nums[g[i]]=vals[i];
    
            }
    
        }
    
        return nums;
    
    }
    
};
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐