Подсчет пар индексов с равными элементами в массиве

Опубликовано: 20 Января, 2022

Дан массив из n элементов. Задача состоит в том, чтобы подсчитать общее количество индексов (i, j) таких, что arr [i] = arr [j] и i! = J
Примеры :

 Ввод: arr [] = {1, 1, 2}
Выход: 1
Поскольку arr [0] = arr [1], пара индексов равна (0, 1)

Ввод: arr [] = {1, 1, 1}
Выход: 3
Поскольку arr [0] = arr [1], пара индексов равна (0, 1), 
(0, 2) и (1, 2)

Ввод: arr [] = {1, 2, 3}
Выход: 0

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Method 1 (Brute Force): 
For each index i, find element after it with same value as arr[i]. Below is the implementation of this approach: 
 

C++

// C++ program to count of pairs with equal
// elements in an array.
#include<bits/stdc++.h>
using namespace std;
 
// Return the number of pairs with equal
// values.
int countPairs(int arr[], int n)
{
    int ans = 0;
 
    // for each index i and j
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
 
            // finding the index with same
            // value but different index.
            if (arr[i] == arr[j])
                ans++;
    return ans;
}
 
// Driven Program
int main()
{
    int arr[] = { 1, 1, 2 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << countPairs(arr, n) << endl;
    return 0;
}

Java

// Java program to count of pairs with equal
// elements in an array.
class GFG {
         
    // Return the number of pairs with equal
    // values.
    static int countPairs(int arr[], int n)
    {
        int ans = 0;
     
        // for each index i and j
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
     
                // finding the index with same
                // value but different index.
                if (arr[i] == arr[j])
                    ans++;
        return ans;
    }
     
    //driver code
    public static void main (String[] args)
    {
        int arr[] = { 1, 1, 2 };
        int n = arr.length;
         
        System.out.println(countPairs(arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to
# count of pairs with equal
# elements in an array.
 
# Return the number of
# pairs with equal values.
def countPairs(arr, n):
 
    ans = 0
 
    # for each index i and j
    for i in range(0 , n):
        for j in range(i + 1, n):
 
            # finding the index
            # with same value but
            # different index.
            if (arr[i] == arr[j]):
                ans += 1
    return ans
 
# Driven Code
arr = [1, 1, 2 ]
n = len(arr)
print(countPairs(arr, n))
 
# This code is contributed
# by Smitha

C#

// C# program to count of pairs with equal
// elements in an array.
using System;
 
class GFG {
         
    // Return the number of pairs with equal
    // values.
    static int countPairs(int []arr, int n)
    {
        int ans = 0;
     
        // for each index i and j
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
     
                // finding the index with same
                // value but different index.
                if (arr[i] == arr[j])
                    ans++;
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 1, 1, 2 };
        int n = arr.Length;
         
        Console.WriteLine(countPairs(arr, n));
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// PHP program to count of
// pairs with equal elements
// in an array.
 
// Return the number of pairs
// with equal values.
function countPairs( $arr, $n)
{
    $ans = 0;
 
    // for each index i and j
    for ( $i = 0; $i < $n; $i++)
        for ( $j = $i + 1; $j < $n; $j++)
 
            // finding the index with same
            // value but different index.
            if ($arr[$i] == $arr[$j])
                $ans++;
    return $ans;
}
 
// Driven Code
$arr = array( 1, 1, 2 );
$n = count($arr);
echo countPairs($arr, $n) ;
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
// Javascript program to count of pairs with equal
// elements in an array.
 
    // Return the number of pairs with equal
    // values.
    function countPairs(arr, n)
    {
        let ans = 0;
       
        // for each index i and j
        for (let i = 0; i < n; i++)
            for (let j = i+1; j < n; j++)
       
                // finding the index with same
                // value but different index.
                if (arr[i] == arr[j])
                    ans++;
        return ans;
    }
      
// Driver code   
 
    let arr = [ 1, 1, 2 ];
    let n = arr.length;
           
    document.write(countPairs(arr, n));
     
    // This code is contributed by susmitakundugoaldanga.
</script>

Выход :

 1

Сложность времени: O (n 2 )
Метод 2 (эффективный подход):
Идея состоит в том, чтобы подсчитать частоту каждого числа, а затем найти количество пар с равными элементами. Предположим, что число x встречается k раз в индексе i 1 , i 2 ,…., I k . Затем выберите любые два индекса i x и i y, которые будут считаться 1 парой. Точно так же i y и i x также могут быть парами. Итак, выберите n C 2 - количество пар таких, что arr [i] = arr [j] = x.
Ниже представлена реализация этого подхода:

Выход :

 1

Сложность времени: O (n)
Источник :
http://stackoverflow.com/questions/26772364/efficient-algorithm-for-counting-number-of-pairs-of-identical-elements-in-an-arr#comment42124861_26772516
Автор статьи - Анудж Чаухан. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ