跳转至

3852. 不同频率的最小数对

题目描述

给你一个整数数组 nums。

从 nums 中找出两个 互不相同 的值 x 和 y，使得：

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

在所有满足条件的数对中：

  • 选择 x 的值尽可能小的数对。
  • 如果存在多个 x 相同的数对，选择 y 的值尽可能小的那个。

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

一个值 x 的 频率 是指它在数组中出现的次数。

 

示例 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

解法

方法一：哈希表

我们用一个哈希表 \(\textit{cnt}\) 来统计每个值在数组中的频率。然后我们找到最小的值 \(x\)，以及比 \(x\) 大且频率与 \(x\) 不同的最小值 \(y\)。如果不存在这样的 \(y\)，则返回 \([-1, -1]\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
6
7
8
9
class Solution:
    def minDistinctFreqPair(self, nums: list[int]) -> list[int]:
        cnt = Counter(nums)
        x = min(cnt.keys())
        min_y = inf
        for y in cnt.keys():
            if y < min_y and cnt[x] != cnt[y]:
                min_y = y
        return [-1, -1] if min_y == inf else [x, min_y]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] minDistinctFreqPair(int[] nums) {
        final int inf = Integer.MAX_VALUE;
        Map<Integer, Integer> cnt = new HashMap<>();
        int x = inf;
        for (int v : nums) {
            cnt.merge(v, 1, Integer::sum);
            x = Math.min(x, v);
        }
        int minY = inf;
        for (int y : cnt.keySet()) {
            if (y < minY && cnt.get(x) != cnt.get(y)) {
                minY = y;
            }
        }
        return minY == inf ? new int[] {-1, -1} : new int[] {x, minY};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> minDistinctFreqPair(vector<int>& nums) {
        const int inf = INT_MAX;
        unordered_map<int, int> cnt;
        int x = inf;

        for (int v : nums) {
            cnt[v]++;
            x = min(x, v);
        }

        int minY = inf;
        for (auto& [y, _] : cnt) {
            if (y < minY && cnt[x] != cnt[y]) {
                minY = y;
            }
        }

        if (minY == inf) {
            return {-1, -1};
        }
        return {x, minY};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minDistinctFreqPair(nums []int) []int {
    const inf = math.MaxInt
    cnt := make(map[int]int)

    for _, v := range nums {
        cnt[v]++
    }

    x := slices.Min(nums)

    minY := inf
    for y := range cnt {
        if y < minY && cnt[x] != cnt[y] {
            minY = y
        }
    }

    if minY == inf {
        return []int{-1, -1}
    }
    return []int{x, minY}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function minDistinctFreqPair(nums: number[]): number[] {
    const inf = Number.MAX_SAFE_INTEGER;
    const cnt = new Map<number, number>();

    let x = inf;
    for (const v of nums) {
        cnt.set(v, (cnt.get(v) ?? 0) + 1);
        x = Math.min(x, v);
    }

    let minY = inf;
    for (const [y] of cnt) {
        if (y < minY && cnt.get(x)! !== cnt.get(y)!) {
            minY = y;
        }
    }

    return minY === inf ? [-1, -1] : [x, minY];
}

评论