Easy

题目描述

给你一个整数数组 nums。

考虑数组中所有不同值 x 和 y 的数对，满足：

  • x < y
  • x 和 y 在 nums 中的频率不同

在所有这样的数对中：

  • 选择 x 值最小的数对
  • 如果有多个数对的 x 相同，选择 y 值最小的数对

返回一个整数数组 [x, y]。如果不存在有效数对，返回 [-1, -1]。

示例 1：

输入：nums = [1,1,2,2,3,4]
输出：[1,3]
解释：
最小值是 1，频率为 2。大于 1 且频率与 1 不同的最小值是 3，频率为 1。
因此答案是 [1, 3]。

示例 2：

输入：nums = [1,5]
输出：[-1,-1]
解释：
两个值的频率相同，所以不存在有效数对。返回 [-1, -1]。

示例 3：

输入：nums = [7]
输出：[-1,-1]
解释：
数组中只有一个值，所以不存在有效数对。返回 [-1, -1]。

提示：

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

解题思路

这道题需要找到满足条件的最小数对 [x, y]，其中 x < y 且两者频率不同。

解题思路：

  1. 统计频率：首先使用哈希表统计每个数字的出现频率。

  2. 获取去重并排序的数组：将所有不同的数字提取出来并排序，这样可以按从小到大的顺序遍历。

  3. 双重循环查找：

    • 外层循环遍历每个数字作为 x
    • 内层循环遍历大于 x 的数字作为 y
    • 检查它们的频率是否不同

  4. 返回结果：由于我们按照从小到大的顺序遍历，第一个找到的满足条件的数对就是答案。

算法复杂度：

  • 时间复杂度：O(n²)，其中 n 是不同数字的个数
  • 空间复杂度：O(n)，用于存储频率统计

这种方法简单直接，由于数据规模较小（最多100个元素），性能完全可以接受。

代码实现

class Solution {
public:
    vector<int> minDistinctFreqPair(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        vector<int> unique_nums;
        for (auto& p : freq) {
            unique_nums.push_back(p.first);
        }
        sort(unique_nums.begin(), unique_nums.end());
        
        for (int i = 0; i < unique_nums.size(); i++) {
            for (int j = i + 1; j < unique_nums.size(); j++) {
                if (freq[unique_nums[i]] != freq[unique_nums[j]]) {
                    return {unique_nums[i], unique_nums[j]};
                }
            }
        }
        
        return {-1, -1};
    }
};

class Solution:
    def minDistinctFreqPair(self, nums: list[int]) -> list[int]:
        from collections import Counter
        
        freq = Counter(nums)
        unique_nums = sorted(freq.keys())
        
        for i in range(len(unique_nums)):
            for j in range(i + 1, len(unique_nums)):
                if freq[unique_nums[i]] != freq[unique_nums[j]]:
                    return [unique_nums[i], unique_nums[j]]
        
        return [-1, -1]

public class Solution {
    public int[] MinDistinctFreqPair(int[] nums) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        
        List<int> uniqueNums = new List<int>(freq.Keys);
        uniqueNums.Sort();
        
        for (int i = 0; i < uniqueNums.Count; i++) {
            for (int j = i + 1; j < uniqueNums.Count; j++) {
                if (freq[uniqueNums[i]] != freq[uniqueNums[j]]) {
                    return new int[] {uniqueNums[i], uniqueNums[j]};
                }
            }
        }
        
        return new int[] {-1, -1};
    }
}

var minDistinctFreqPair = function(nums) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    const uniqueNums = Array.from(freq.keys()).sort((a, b) => a - b);
    
    for (let i = 0; i < uniqueNums.length; i++) {
        for (let j = i + 1; j < uniqueNums.length; j++) {
            if (freq.get(uniqueNums[i]) !== freq.get(uniqueNums[j])) {
                return [uniqueNums[i], uniqueNums[j]];
            }
        }
    }
    
    return [-1, -1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)n 为不同数字的个数，需要双重循环查找数对
空间复杂度O(n)存储频率统计和去重数组