C++程序 最大化通过旋转给定数组来对应相同元素的计数

给定两个包含 N 个整数的数组 arr1[] 和 arr2[] ，其中 arr1[] 具有不同的元素。任务是通过对数组 arr1[] 执行循环左移或右移来查找给定数组中对应相同元素的最大计数。

示例：

输入： arr1[] = { 6, 7, 3, 9, 5 }, arr2[] = { 7, 3, 9, 5, 6 }

输出： 5

解释：

通过将数组 arr1[] 循环左移1次。

更新后的数组 arr1[] = {7, 3, 9, 5, 6}。

这个旋转包含数组 arr1[] 和 arr2[] 之间相同元素的最大数量。

输入： arr1[] = {1, 3, 2, 4}, arr2[] = {4, 2, 3, 1}

输出： 2

解释：

通过将数组 arr1[] 循环左移1次。

更新后的数组 arr1[] = {3, 2, 4, 1}。

这个旋转包含数组 arr1[] 和 arr2[] 之间相同元素的最大数量。

方法： 可以使用贪心方法解决此问题。具体步骤如下：

1. 在一个数组（称为 store[] ）中存储数组 arr2[] 的所有元素的位置。
2. 对于数组 arr1[] 中的每个元素，执行以下操作：

• 找到当前元素在 arr2[] 中的位置与在 arr1[] 中的位置之间的差异（称为 diff ）。
• 如果 diff 小于0，则将 diff 更新为 (N-diff) 。
• 将当前差异 diff 的频率存储在一个map中。
  3. 经过上述步骤，map中存储的最大频率即为在 arr1[] 旋转后相等元素的最大数量。

下面是上述方法的实现：

// 上面方法的C++程序 
#include <bits/stdc++.h>
using namespace std;
  
// 打印最大相同元素的函数 
void maximumEqual(int a[], int b[],
                  int n)
{
  
    // 存储数组b中元素的索引的向量 
    vector<int> store(1e5);
  
    // 存储数组B位置的向量 
    for (int i = 0; i < n; i++) {
        store[b[i]] = i + 1;
    }
  
    // 频率数组来计算有相似距离差的元素数 
    vector<int> ans(1e5);
  
    // 遍历数组arr1 
    for (int i = 0; i < n; i++) {
  
        // 计算当前元素与相等的元素之间的移动距离 
        int d = abs(store[a[i]]
                    - (i + 1));
  
        // 如果d小于0 
        if (store[a[i]] < i + 1) {
            d = n - d;
        }
  
        // 存储当前元素的频率 
        ans[d]++;
    }
  
    int finalans = 0;
  
    // 计算已存储元素的最大频率 
    for (int i = 0; i < 1e5; i++)
        finalans = max(finalans,
                       ans[i]);
  
    // 打印最大的相同元素数 
    cout << finalans << "
";
}
  
// 主函数
int main()
{
    // 给出两个数组 
    int A[] = { 6, 7, 3, 9, 5 };
    int B[] = { 7, 3, 9, 5, 6 };
  
    int size = sizeof(A) / sizeof(A[0]);
  
    // 调用方法 
    maximumEqual(A, B, size);
    return 0;
}  

输出:

5

时间复杂度: O(N)

辅助空间: O(N)