跳转至

3400. 右移后的最大匹配索引数 🔒

题目描述

给定两个长度相同的整数数组 nums1 和 nums2。

如果 nums1[i] == nums2[i] 则认为下标 i 是 匹配 的。

返回在 nums1 上进行任意次数 右移 后 最大 的 匹配 下标数量。

右移 是对于所有下标，将位于下标 i 的元素移动到 (i + 1) % n。

 

示例 1：

输入：nums1 = [3,1,2,3,1,2], nums2 = [1,2,3,1,2,3]

输出：6

解释：

如果我们右移 nums1 2 次，它变为 [1, 2, 3, 1, 2, 3]。每个下标都匹配，所以输出为 6。

示例 2：

输入：nums1 = [1,4,2,5,3,1], nums2 = [2,3,1,2,4,6]

输出：3

解释：

如果我们右移 nums1 3 次，它变为 [5, 3, 1, 1, 4, 2]。下标 1，2，4 匹配，所以输出为 3。

 

提示：

  • nums1.length == nums2.length
  • 1 <= nums1.length, nums2.length <= 3000
  • 1 <= nums1[i], nums2[i] <= 109

解法

方法一：枚举

我们可以枚举右移的次数 $k$，其中 $0 \leq k \lt n$。对于每一个 $k$，我们可以计算出右移 $k$ 次后的数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的匹配下标数量，取最大值作为答案即可。

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

1
2
3
4
5
6
7
8
class Solution:
    def maximumMatchingIndices(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        ans = 0
        for k in range(n):
            t = sum(nums1[(i + k) % n] == x for i, x in enumerate(nums2))
            ans = max(ans, t)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int maximumMatchingIndices(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int ans = 0;
        for (int k = 0; k < n; ++k) {
            int t = 0;
            for (int i = 0; i < n; ++i) {
                if (nums1[(i + k) % n] == nums2[i]) {
                    ++t;
                }
            }
            ans = Math.max(ans, t);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumMatchingIndices(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int ans = 0;
        for (int k = 0; k < n; ++k) {
            int t = 0;
            for (int i = 0; i < n; ++i) {
                if (nums1[(i + k) % n] == nums2[i]) {
                    ++t;
                }
            }
            ans = max(ans, t);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func maximumMatchingIndices(nums1 []int, nums2 []int) (ans int) {
    n := len(nums1)
    for k := range nums1 {
        t := 0
        for i, x := range nums2 {
            if nums1[(i+k)%n] == x {
                t++
            }
        }
        ans = max(ans, t)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maximumMatchingIndices(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    let ans: number = 0;
    for (let k = 0; k < n; ++k) {
        let t: number = 0;
        for (let i = 0; i < n; ++i) {
            if (nums1[(i + k) % n] === nums2[i]) {
                ++t;
            }
        }
        ans = Math.max(ans, t);
    }
    return ans;
}

评论