4065. 移除不同值重排数组

难度简单

题目描述

给你一个整数数组 nums。

初始时，你有一个空数组 ans。重复执行以下操作，直到 nums 变为空：

找出当前 nums 中 所有不同 的值。
将当前 nums 中每个不同的值各移除一个，并按升序将这些值依次添加到 ans 中。

返回数组 ans。

示例 1：

输入： nums = [3,1,3,2,1,3]

输出： [1,2,3,1,3,3]

解释：

操作	添加到 `ans` 的值	操作后的 `nums`	操作后的 `ans`
1	1, 2, 3	`[3, 1, 3]`	`[1, 2, 3]`
2	1, 3	`[3]`	`[1, 2, 3, 1, 3]`
3	3	`[]`	`[1, 2, 3, 1, 3, 3]`

此时 nums 已为空，因此答案为 [1, 2, 3, 1, 3, 3]。

示例 2：

输入： nums = [7,7,4,4,4]

输出： [4,7,4,7,4]

解释：

操作	添加到 `ans` 的值	操作后的 `nums`	操作后的 `ans`
1	4, 7	`[7, 4, 4]`	`[4, 7]`
2	4, 7	`[4]`	`[4, 7, 4, 7]`
3	4	`[]`	`[4, 7, 4, 7, 4]`

此时 nums 已为空，因此答案为 [4, 7, 4, 7, 4]。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

解法

方法一：计数

思考

\(n\) 和每个元素都不超过 \(100\)，按题意一轮轮取出剩余的不同值是来得及的。每一轮都要收集当前还在的值并按升序各删一个，若直接在原数组里查找再删除，下标会不断挪动。

一个值被取走的次数就是它的出现次数，每一轮内部的先后只由数值大小决定，与原来的下标无关。

因此先按值计数。值域是 \([1,m]\)，从小到大扫描，次数仍为正就写入答案并减一。外层重复到答案长度等于 \(n\)，每一遍扫描对应一轮操作。

设 \(m=\max(\textit{nums})\)， \(\textit{cnt}[x]\) 为值 \(x\) 的出现次数。第 \(k\) 轮（从 \(0\) 计）按升序取走所有当时仍有剩余的值，也就是最初出现次数大于 \(k\) 的那些值。

用长度为 \(m+1\) 的数组记下次数。答案还不满 \(n\) 个元素时，把 \(x\) 从 \(1\) 扫到 \(m\)： \(\textit{cnt}[x]>0\) 就把 \(x\) 追加进答案，并把次数减一。一轮扫描对应一次操作，追加的顺序就是升序。

时间复杂度 \(O(nm)\)，空间复杂度 \(O(m)\)。

Python3JavaC++GoTypeScript

class Solution:
    def rearrangeArray(self, nums: list[int]) -> list[int]:
        mx = max(nums)
        cnt = [0] * (mx + 1)
        for x in nums:
            cnt[x] += 1

        ans = []
        while len(ans) < len(nums):
            for x in range(1, mx + 1):
                if cnt[x]:
                    ans.append(x)
                    cnt[x] -= 1
        return ans

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int[] cnt = new int[mx + 1];
        for (int x : nums) {
            cnt[x]++;
        }

        int[] ans = new int[nums.length];
        int idx = 0;
        while (idx < nums.length) {
            for (int x = 1; x <= mx; x++) {
                if (cnt[x] > 0) {
                    ans[idx++] = x;
                    cnt[x]--;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int mx = ranges::max(nums);
        vector<int> cnt(mx + 1);
        for (int x : nums) {
            cnt[x]++;
        }

        vector<int> ans;
        while (ans.size() < nums.size()) {
            for (int x = 1; x <= mx; x++) {
                if (cnt[x]) {
                    ans.push_back(x);
                    cnt[x]--;
                }
            }
        }
        return ans;
    }
};

func rearrangeArray(nums []int) []int {
    mx := slices.Max(nums)

    cnt := make([]int, mx+1)
    for _, x := range nums {
        cnt[x]++
    }

    ans := make([]int, 0, len(nums))
    for len(ans) < len(nums) {
        for x := 1; x <= mx; x++ {
            if cnt[x] > 0 {
                ans = append(ans, x)
                cnt[x]--
            }
        }
    }
    return ans
}

function rearrangeArray(nums: number[]): number[] {
    const mx = Math.max(...nums);
    const cnt = new Array(mx + 1).fill(0);

    for (const x of nums) {
        cnt[x]++;
    }

    const ans: number[] = [];
    while (ans.length < nums.length) {
        for (let x = 1; x <= mx; x++) {
            if (cnt[x]) {
                ans.push(x);
                cnt[x]--;
            }
        }
    }
    return ans;
}

4065. 移除不同值重排数组

题目描述

解法

方法一：计数

评论