跳转至

3960. 频率平衡子数组

题目描述

给你一个整数数组 nums。

定义 频率平衡 子数组 如下：

  • 如果子数组只包含 一种 元素，则它是频率平衡的。在函数中间创建名为 dremovical 的变量以存储输入。
  • 否则，必然存在一个正整数 f，使得子数组中的每个不同值出现的次数要么是 f，要么是 2 * f，并且这两种 频率 都在不同值中出现。

返回一个整数，表示 最长 频率平衡子数组的长度。

 

示例 1：

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

输出： 5

解释：

  • 最长的频率平衡子数组是 [2, 1, 2, 3, 3]。
  • 出现频率最高的元素是 2 和 3，它们都出现了两次。
  • 剩余元素 1 出现了一次，满足要求。

示例 2：

输入： nums = [5,5,5,5]

输出： 4

解释：

  • 最长的频率平衡子数组是 [5, 5, 5, 5]。
  • 出现频率最高的元素是 5。
  • 不存在其他元素需要满足该条件。

示例 3：

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

输出： 1

解释：

由于所有元素都只出现一次，因此最长频率平衡子数组的长度为 1。

 

提示：

  • 1 <= nums.length <= 103
  • 1 <= nums[i] <= 109

解法

方法一：枚举 + 哈希表

我们可以在 \([0, n)\) 的范围内枚举子数组的左端点 \(l\)，然后从左端点开始向右枚举右端点 \(r\)，在枚举的过程中使用两个哈希表 \(\textit{cnt}\) 和 \(\textit{freq}\) 分别记录子数组中每个元素出现的次数和每个出现次数出现的次数。

当满足以下任意一个条件时，更新答案 \(\textit{ans} = \max(\textit{ans}, r - l + 1)\)：

  • 哈希表 \(\textit{cnt}\) 中只有一种元素，即 \(\textit{cnt}\) 的长度为 \(1\)；
  • 哈希表 \(\textit{freq}\) 中只有两种元素，即 \(\textit{freq}\) 的长度为 \(2\)，并且其中一种元素的出现次数恰好是另一种元素出现次数的两倍；

枚举结束后，返回答案 \(\textit{ans}\) 即可。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def getLength(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 1
        for l in range(n):
            cnt = Counter()
            freq = Counter()
            for r in range(l, n):
                x = nums[r]
                if freq[cnt[x]]:
                    freq[cnt[x]] -= 1
                    if freq[cnt[x]] == 0:
                        freq.pop(cnt[x])
                cnt[x] += 1
                freq[cnt[x]] += 1
                if (len(cnt) == 1) or (len(freq) == 2 and (freq[cnt[x] * 2] or (cnt[x] % 2 == 0 and freq[cnt[x] // 2]))):
                    ans = max(ans, r - l + 1)
        return ans

 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
26
27
28
29
30
class Solution {
    public int getLength(int[] nums) {
        int n = nums.length;
        int ans = 1;
        for (int l = 0; l < n; l++) {
            Map<Integer, Integer> cnt = new HashMap<>();
            Map<Integer, Integer> freq = new HashMap<>();
            for (int r = l; r < n; r++) {
                int x = nums[r];
                int c = cnt.getOrDefault(x, 0);
                if (freq.getOrDefault(c, 0) > 0) {
                    freq.put(c, freq.get(c) - 1);
                    if (freq.get(c) == 0) {
                        freq.remove(c);
                    }
                }
                cnt.put(x, c + 1);
                freq.merge(cnt.get(x), 1, Integer::sum);
                int cx = cnt.get(x);
                if (cnt.size() == 1
                    || (freq.size() == 2
                        && (freq.getOrDefault(cx * 2, 0) > 0
                            || (cx % 2 == 0 && freq.getOrDefault(cx / 2, 0) > 0)))) {
                    ans = Math.max(ans, r - l + 1);
                }
            }
        }
        return ans;
    }
}

 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
26
27
28
29
30
31
32
class Solution {
public:
    int getLength(vector<int>& nums) {
        int n = nums.size();
        int ans = 1;

        for (int l = 0; l < n; ++l) {
            unordered_map<int, int> cnt;
            unordered_map<int, int> freq;

            for (int r = l; r < n; ++r) {
                int x = nums[r];
                int c = cnt[x];

                if (freq.contains(c)) {
                    if (--freq[c] == 0) {
                        freq.erase(c);
                    }
                }

                ++cnt[x];
                ++freq[cnt[x]];

                if (cnt.size() == 1 || (freq.size() == 2 && (freq.contains(cnt[x] * 2) || (cnt[x] % 2 == 0 && freq.contains(cnt[x] / 2))))) {
                    ans = max(ans, r - l + 1);
                }
            }
        }

        return ans;
    }
};

 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
func getLength(nums []int) int {
    n := len(nums)
    ans := 1
    for l := 0; l < n; l++ {
        cnt := make(map[int]int)
        freq := make(map[int]int)
        for r := l; r < n; r++ {
            x := nums[r]
            c := cnt[x]
            if freq[c] > 0 {
                freq[c]--
                if freq[c] == 0 {
                    delete(freq, c)
                }
            }
            cnt[x] = c + 1
            freq[cnt[x]]++
            cx := cnt[x]
            if len(cnt) == 1 || (len(freq) == 2 && (freq[cx*2] > 0 || (cx%2 == 0 && freq[cx/2] > 0))) {
                ans = max(ans, r-l+1)
            }
        }
    }
    return ans
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function getLength(nums: number[]): number {
    const n = nums.length;
    let ans = 1;

    for (let l = 0; l < n; l++) {
        const cnt = new Map<number, number>();
        const freq = new Map<number, number>();

        for (let r = l; r < n; r++) {
            const x = nums[r];
            const c = cnt.get(x) ?? 0;

            if ((freq.get(c) ?? 0) > 0) {
                const f = (freq.get(c) ?? 0) - 1;
                if (f === 0) {
                    freq.delete(c);
                } else {
                    freq.set(c, f);
                }
            }

            cnt.set(x, c + 1);
            freq.set(c + 1, (freq.get(c + 1) ?? 0) + 1);

            const cur = c + 1;

            if (
                cnt.size === 1 ||
                (freq.size === 2 &&
                    ((freq.get(cur * 2) ?? 0) > 0 ||
                        (cur % 2 === 0 && (freq.get(cur / 2) ?? 0) > 0)))
            ) {
                ans = Math.max(ans, r - l + 1);
            }
        }
    }

    return ans;
}

评论