Массив дахь ижил элементтэй индексийн хосыг тоолох  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Atlassian Citadel Facebook-ийн Intuit Snapdeal Square Yandex
Array Хаш хайх Ангилах

Бид өгсөн гэж бодъё бүхэл тоо массив. “Массив дахь ижил элементтэй индексийн хосыг тоолох” асуудал нь хос индекс байхгүйг олохыг хүсдэг (би, ж) ийм байдлаар 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. Мэдүүлэх a газрын зураг.
  2. Хөндлөн гар массив элемент тус бүрийн давтамжийг тоолж газрын зураг дээр хадгалах.
  3. Гаралтыг 0 болгож тохируулна уу.
  4. Газрын зургийг дайран өнгөрч, элемент бүрийн давтамжийг газрын зургаас авна уу.
  5. Гаралт + = (VAL * (VAL - 1)) / 2, VAL нь элемент бүрийн давтамж юм.
  6. Гаралтыг буцаах.

Тайлбар

Бид өгсөн массив бүхэл тооноос бид нийт үгүйг олохыг хүссэн. массив дээр байгаа хосуудын индексүүд ижил биш боловч тэдгээр индексүүдийн элементүүд ижил байх ёстой. Тиймээс бид ашиглах болно Хаширч байна үүний төлөө. Hashing бол нэмэлт элемент ашиглан эдгээр бүх элементүүд дээр очиж үзэх хүчирхийллийн хүчнээс илүү сайн арга юм O (n2). Тиймээс бид үүнээс зайлсхийж байна.

Бид газрын зураг зарлаж, элемент бүрийг сонгож, элемент бүрийн давтамжийг газрын зураг дээр тоолж хадгална, хэрэв тэр газрын зураг дээр байгаа бол байрлалыг нь байрлуул, хэрэв байгаа бол давтамжаа 1-ээр л нэмэгдүүлнэ.

мөн үзнэ үү
Leetcode шийдлүүдийн хослолыг солих

Хосолсон томъёог ашиглахын тулд тоо бүрийн давтамжийг тоолох хэрэгтэй. Бид тэнцүү элементүүдийн өгөгдсөн нөхцлийг хангасан хэд хэдэн хосыг сонгох болно, гэхдээ тэдгээрийн индексүүд биш юм. Массивт байгаа дурын тоо kth индекс хүртэлх дурын индекс дээр k удаа гарч ирнэ гэж бид үзэж болно. Дараа нь дурын хоёр индексийг сонгоно уу ai болон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" массив дахь элементүүдийн тоо юм.