数组替换算法优化：最小化最大值

题目描述： 给你一个长度为 n 的数组 nums，其中 nums[i] 的取值范围是 [0, n - 1]。请你原地修改 nums，以使所有编号互不相同的情况下，最小化 max(nums)。请你在完成最后一个操作后，返回数组中最大值。

输入格式： 第一行包含一个整数 n。第二行包含 n 个整数，表示数组 nums。

输出格式： 输出一个整数，表示数组中最大值。

数据范围： 1≤n≤10^5

输入样例 1： 4 2 2 0 1

输出样例 1： 3

样例 1 解释： 将下标为 0 的元素替换为 3，nums = [3,2,0,1]，max(nums) = 3。将下标为 1 的元素替换为 3，nums = [3,3,0,1]，max(nums) = 3。将下标为 0 的元素替换为 2，nums = [2,3,0,1]，max(nums) = 3。将下标为 1 的元素替换为 2，nums = [2,2,0,1]，max(nums) = 2。没有办法继续替换，最大值为 2。

输入样例 2： 3 1 1 2

输出样例 2： 2

样例 2 解释： 将下标为 0 的元素替换为 0，nums = [0,1,2]，max(nums) = 2。没有办法继续替换，最大值为 2。

算法 1：

遍历所有数，将相同的数全部置为 -1，然后进行排序；
重新从小到大排号

C++ 代码：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                nums[j] = -1;
            }
        }
    }
    sort(nums, nums + n);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] != -1) {
            nums[i] = cnt;
            cnt++;
        }
    }
    int max_num = 0;
    for (int i = 0; i < n; i++) {
        max_num = max(max_num, nums[i]);
    }
    cout << max_num << endl;
    return 0;
}

算法 2： 可以先统计下标出现的次数，然后将 nums 中重复出现的数字全找到，记录下这些位置，然后按照 nums 的大小从小到大从 0 开始数。

C++ 代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
        cnt[nums[i]]++;
    }
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        if (cnt[i] > 1) {
            for (int j = 0; j < n; j++) {
                if (nums[j] == i) {
                    pos.push_back(j);
                }
            }
        }
    }
    sort(pos.begin(), pos.end(), [&](int a, int b) {
        return nums[a] < nums[b];
    });
    int num = 0;
    for (int i = 0; i < pos.size(); i++) {
        nums[pos[i]] = num;
        num++;
    }
    int max_num = 0;
    for (int i = 0; i < n; i++) {
        max_num = max(max_num, nums[i]);
    }
    cout << max_num << endl;
    return 0;
}

算法 3： 一个很 tricky 的做法，我也不会。。。

C++ 代码：

// 算法3代码

总结： 本文介绍了三种解决数组替换问题的算法，分别从不同的角度出发，实现了最小化数组最大值的目标。读者可以根据自己的需要选择合适的算法。