数组中具有相等元素的索引对的计数  


难度级别 易得奖学金
经常问 亚马逊 Atlassian的 堡垒 Facebook 意会 Snapdeal 广场 Yandex的
排列 哈希 搜索 排序

假设我们给了 整数 排列。 问题“在数组中具有相等元素的索引对的计数”要求找出索引对的编号(arr [i] = arr [j] 以及 i 不等于 j.

使用案列  

arr[] = {2,3,1,2,3,1,4}
3

说明

索引对为:(0,3),(1,4),(2,5)

数组中具有相等元素的索引对的计数

arr[] = {3, 3, 1, 4}
1

说明

对索引为:(0,1)

算法  

  1. 声明一个 地图位置.
  2. 遍历 排列 并将每个元素的频率计数并存储到地图中。
  3. 将输出设置为0。
  4. 遍历地图,并从地图中获取每个元素的频率。
  5. 输出+ =(VAL *(VAL – 1))/ 2,VAL是每个元素的频率。
  6. 返回输出。

说明

我们给了 排列 整数,我们要求找出总数。 数组中存在的对对,使得它们的索引不相同,但这些索引上的元素应相同。 因此,我们将使用 哈希 为了它。 散列是比蛮力法更好的方法,在蛮力法中,我们必须花额外的时间访问所有这些元素。 2)。 因此,我们正在避免这种情况。

我们将声明一个地图,拾取每个元素,计数每个元素的频率并将其存储在地图中(如果已经存在于地图中),为其放置一个位置,如果它已经存在则将其频率增加1。

参见
成对的交换节点Leetcode解决方案

要使用组合公式,我们必须计算每个数字的频率。 我们将选择满足给定条件的相等元素但不满足其索引的几对。 我们可以假设数组中存在的任何数字在第k个索引之前的任何索引处都出现k次。 然后选择任意两个索引i 的网络y 将被计为1对。 同样,y 的网络x 也可以成对。 所以, nC2 是用于找出arr [i] = arr [j]也等于x的对数的公式。

遍历数组之后,将每个元素及其出现的位置放入地图中,我们将遍历该地图,拾取元素的每个频率并对其应用公式,然后将输出加起来并存储在输出中。 我们必须不断重复它,直到遍历所有元素及其频率并对其执行操作为止。 最后,我们将返回该输出。

C ++代码查找数组中具有相等元素的索引对的数量  

#include<iostream>
#include<unordered_map>

using namespace std;

int getNoOfPairs(int arr[], int n)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    int output = 0;
    for (auto it=MAP.begin(); it!=MAP.end(); it++)
    {
        int VAL = it->second;
        output += (VAL * (VAL - 1))/2;
    }
    return output;
}
int main()
{
    int arr[] = {2,3,1,2,3,1,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNoOfPairs(arr, n) << endl;
    return 0;
}
3

Java代码查找数组中具有相等元素的索引对的计数  

import java.util.HashMap;
import java.util.Map;

class countIndexPair
{
    public static int getNoOfPairs(int arr[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<>();

        for(int i = 0; i < n; i++)
        {
            if(MAP.containsKey(arr[i]))
                MAP.put(arr[i],MAP.get(arr[i]) + 1);
            else
                MAP.put(arr[i], 1);
        }
        int output=0;
        for(Map.Entry<Integer,Integer> entry : MAP.entrySet())
        {
            int VAL = entry.getValue();
            output += (VAL * (VAL - 1)) / 2;
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,1,2,3,1,4};
        System.out.println(getNoOfPairs(arr,arr.length));
    }
}
3

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

参见
迭代预遍历

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。