解题思路

这道题目可以使用遍历+哈希表的方法解决。对于每个数组元素，我们可以：

  1. 将其作为可能被修改成的目标值
  2. 统计原数组中与该值相同的元素个数
  3. 由于可以修改一个其他的数，所以最终结果是该值的出现次数+1（如果还有其他不同的数）

代码

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

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    unordered_map<int, int> count;
    for(int num : nums) {
        count[num]++;
    }
    
    int maxCount = 0;
    for(auto [num, freq] : count) {
        maxCount = max(maxCount, freq + (n > freq ? 1 : 0));
    }
    
    cout << maxCount << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Map<Integer, Integer> count = new HashMap<>();
        for(int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int maxCount = 0;
        for(Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int freq = entry.getValue();
            maxCount = Math.max(maxCount, freq + (n > freq ? 1 : 0));
        }
        
        System.out.println(maxCount);
    }
}

n = int(input())
nums = list(map(int, input().split()))

count = {}
for num in nums:
    count[num] = count.get(num, 0) + 1

max_count = 0
for num, freq in count.items():
    max_count = max(max_count, freq + (1 if n > freq else 0))

print(max_count)

算法及复杂度

  • 算法：哈希。
  • 时间复杂度：，其中 n 为数组长度。
  • 空间复杂度：，需要哈希表存储每个数字的出现次数。