배열에서 동일한 요소가있는 인덱스 쌍의 수


난이도 쉽게
자주 묻는 질문 아마존 골드 피처 페이스북 서비스 인튜이트 스냅 딜 사각형. Yandex 주차
배열 해시 수색 정렬

가정 해 보겠습니다. 정수 정렬. "배열에서 동일한 요소를 가진 인덱스 쌍의 개수"문제는 인덱스 쌍의 수를 알아 내도록 요청합니다 (나는 j) 그런 식으로 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 씩 증가시킵니다.

조합 공식을 사용하려면 각 숫자의 빈도를 계산해야합니다. 동일한 요소의 주어진 조건을 만족하지만 인덱스가 아닌 여러 쌍을 선택합니다. 배열에있는 숫자는 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) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.