难度中等
题目描述
给你一个 下标从 1 开始 的整数数组 nums。
你可以选择两个 不同 的值 x 和 y，并 最多 执行一次以下操作：
返回执行操作后，相邻且相等的元素对数量的 最大值 。
示例 1：
输入： nums = [1,2,3,2]
输出： 2
解释：
- 一种最优方案是选择
x = 3 和 y = 2。 - 得到的数组为
[1, 2, 2, 2]。 - 有 2 对相邻且相等的元素：
(nums[2], nums[3]) 和 (nums[3], nums[4])。 - 因此，答案为 2。
示例 2：
输入： nums = [1,2,1,2,1]
输出： 4
解释：
- 一种最优方案是选择
x = 1 和 y = 2。 - 得到的数组为
[2, 2, 2, 2, 2]。 - 有 4 对相邻且相等的元素：
(nums[1], nums[2])、(nums[2], nums[3])、(nums[3], nums[4]) 和 (nums[4], nums[5])。 - 因此，答案为 4。
示例 3：
输入： nums = [1,1,1]
输出： 2
解释：
- 一种最优方案是不执行任何操作。
- 因此，得到的数组仍为
[1, 1, 1]。 - 有 2 对相邻且相等的元素：
(nums[1], nums[2]) 和 (nums[2], nums[3])。 - 因此，答案为 2。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 109
解法
方法一：哈希表
思考
\(n\) 可以到 \(10^5\)，元素可以到 \(10^9\)。把每一对不同的 \(x,y\) 都替换一遍再重数相邻对，候选太多。
已经相邻且相等的两个位置，无论把哪个值整体换成另一个值，都会继续相等。一次替换只会让原先取值恰好是这对 \(x,y\) 的相邻位置变成相等，别的无序对对应的是另一次操作。
因此先数出原本相等的相邻位置，再按无序对统计不相等的相邻位置，把出现次数的最大值加回去。不操作时这个最大值是 \(0\)。
相邻并且已经相等的位置，在任意一次替换之后仍然相等：两个位置同为 \(x\) 时会一起变成 \(y\)，其余值保持不变。把这样的位置对个数记为 \(\textit{ans}\)。
一次操作选定两个不同的值，把其中一个全部换成另一个。新变成相等的相邻位置，原先两个值只能就是被选中的这一对。对相邻且不相等的 \(x,y\)，把较小值放在前面，编码成
\[ \textit{key}=(x\ll 30)\mid y. \]
\(x,y\le 10^9\)，这个键落在 \(64\) 位整数里。 \(\textit{cnt}[\textit{key}]\) 是同一对值作为相邻位置出现的次数。选中这一对时，新增的相等相邻对个数就是 \(\textit{cnt}[\textit{key}]\)。取所有计数的最大值 \(\textit{mx}\)；一次都不操作时 \(\textit{mx}=0\)。答案是 \(\textit{ans}+\textit{mx}\)。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def maxEqualAdjacentPairs(self, nums: list[int]) -> int:
cnt = defaultdict(int)
ans = mx = 0
for x, y in pairwise(nums):
if x == y:
ans += 1
else:
if x > y:
x, y = y, x
key = x << 30 | y
cnt[key] += 1
mx = max(mx, cnt[key])
ans += mx
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 | class Solution {
public int maxEqualAdjacentPairs(int[] nums) {
Map<Long, Integer> cnt = new HashMap<>();
int ans = 0, mx = 0;
for (int i = 0; i + 1 < nums.length; i++) {
int x = nums[i], y = nums[i + 1];
if (x == y) {
ans++;
} else {
if (x > y) {
int t = x;
x = y;
y = t;
}
long key = ((long) x << 30) | y;
int v = cnt.merge(key, 1, Integer::sum);
mx = Math.max(mx, v);
}
}
ans += mx;
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int maxEqualAdjacentPairs(vector<int>& nums) {
unordered_map<long long, int> cnt;
int ans = 0, mx = 0;
for (int i = 0; i + 1 < nums.size(); i++) {
int x = nums[i], y = nums[i + 1];
if (x == y) {
ans++;
} else {
if (x > y) {
swap(x, y);
}
long long key = ((long long) x << 30) | y;
mx = max(mx, ++cnt[key]);
}
}
ans += mx;
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func maxEqualAdjacentPairs(nums []int) int {
cnt := map[int64]int{}
ans, mx := 0, 0
for i := 0; i+1 < len(nums); i++ {
x, y := nums[i], nums[i+1]
if x == y {
ans++
} else {
if x > y {
x, y = y, x
}
key := int64(x)<<30 | int64(y)
cnt[key]++
if cnt[key] > mx {
mx = cnt[key]
}
}
}
ans += mx
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function maxEqualAdjacentPairs(nums: number[]): number {
const cnt = new Map<bigint, number>();
let ans = 0;
let mx = 0;
for (let i = 0; i + 1 < nums.length; i++) {
let x = nums[i];
let y = nums[i + 1];
if (x === y) {
ans++;
} else {
if (x > y) {
[x, y] = [y, x];
}
const key = (BigInt(x) << 30n) | BigInt(y);
cnt.set(key, (cnt.get(key) || 0) + 1);
mx = Math.max(mx, cnt.get(key)!);
}
}
ans += mx;
return ans;
}
|