数组中具有相等元素的索引对的数量 | 系列 2
原文：https://www.geeksforgeeks.org/count-of-index-pairs-with-equal-elements-in-an-array-set-2/
给定N个元素的数组arr[]。 任务是计算索引(i, j)的总数，以使arr[i] = arr[j]和i != j。
示例：
输入：
arr[] = {1, 2, 1, 1}输出：3
说明：
在数组中
arr[0] = arr[2] = arr [3]。有效对为
（0, 2),(0, 3)和(2, 3)。输入：
arr[] = {2, 2, 3, 2, 3}输出：4
说明：
在数组中
arr[0] = arr[1] = arr[3]和arr[2] = arr[4]。所以有效对是
(0, 1)，(0, 3)，(1, 3)，(2, 4)。
对于朴素和有效的方法，请参阅本文的先前文章。
更好的方法 - 使用两个指针：这个想法是对给定的数组排序，和具有相同元素的索引差。 步骤如下：
-
排序给定的数组。
-
将两个指针
left和right分别初始化为 0 和 1。 -
现在直到
right小于N，执行以下操作：-
如果索引
left和right的元素相同，则增加right指针并将right指针和left指针的差加到最终计数中。 -
否则将
right值更新到left。
-
-
完成上述步骤后，打印计数值。
下面是上述方法的实现：
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the pair in
// the array arr[]
int countPairs(int arr[], int n)
{
int ans = 0;
// Sort the array
sort(arr, arr + n);
// Initialize two pointers
int left = 0, right = 1;
while (right < n) {
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 2, 3, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that counts the pair in
// the array arr[]
static int countPairs(int arr[], int n)
{
int ans = 0;
// Sort the array
Arrays.sort(arr);
// Initialize two pointers
int left = 0, right = 1;
while (right < n)
{
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 2, 3, 2, 3 };
int N = arr.length;
// Function call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach
# Function that counts the pair in
# the array arr[]
def countPairs(arr, n):
ans = 0
# Sort the array
arr.sort()
# Initialize two pointers
left = 0
right = 1;
while (right < n):
if (arr[left] == arr[right]):
# Add all valid pairs to answer
ans += right - left;
else:
left = right;
right += 1
# Return the answer
return ans
# Driver Code
if __name__ == "__main__":
# Given array arr[]
arr = [2, 2, 3, 2, 3]
N = len(arr)
# Function call
print (countPairs(arr, N))
# This code is contributed by Chitranayal
C
// C# program for the above approach
using System;
class GFG{
// Function that counts the pair in
// the array []arr
static int countPairs(int []arr, int n)
{
int ans = 0;
// Sort the array
Array.Sort(arr);
// Initialize two pointers
int left = 0, right = 1;
while (right < n)
{
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 2, 2, 3, 2, 3 };
int N = arr.Length;
// Function call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by sapnasingh4991
输出：
4
时间复杂度：O(N * log N)。
辅助空间：O(1)。
高效方法 – 使用单个遍历：想法是使用 散列 并更新频率大于 1 的每对的计数。以下是步骤：
-
创建一个
unordered_map M，以将每个元素的频率存储在数组中。 -
遍历给定的数组，并继续更新
M中每个元素的频率。 -
在上述步骤中更新频率时，如果任何元素的频率大于 0，则将该频率计数为最终计数。
-
完成上述步骤后，打印偶对数量。
下面是上述方法的实现：
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that count the pairs having
// same elements in the array arr[]
int countPairs(int arr[], int n)
{
int ans = 0;
// Hash map to keep track of
// occurences of elements
unordered_map<int, int> count;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Check if occurence of arr[i] > 0
// add count[arr[i]] to answer
if (count[arr[i]] != 0)
ans += count[arr[i]];
// Increase count of arr[i]
count[arr[i]]++;
}
// Return the result
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that count the pairs having
// same elements in the array arr[]
static int countPairs(int arr[], int n)
{
int ans = 0;
// Hash map to keep track of
// occurences of elements
HashMap<Integer,
Integer> count = new HashMap<>();
// Traverse the array arr[]
for (int i = 0; i < n; i++)
{
// Check if occurence of arr[i] > 0
// add count[arr[i]] to answer
if(count.containsKey(arr[i]))
{
ans += count.get(arr[i]);
count.put(arr[i], count.get(arr[i]) + 1);
}
else
{
count.put(arr[i], 1);
}
}
// Return the result
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 1, 1 };
int N = arr.length;
// Function call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by PrinciRaj1992
C
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that count the pairs having
// same elements in the array []arr
static int countPairs(int []arr, int n)
{
int ans = 0;
// Hash map to keep track of
// occurences of elements
Dictionary<int,
int> count = new Dictionary<int,
int>();
// Traverse the array []arr
for (int i = 0; i < n; i++)
{
// Check if occurence of arr[i] > 0
// add count[arr[i]] to answer
if(count.ContainsKey(arr[i]))
{
ans += count[arr[i]];
count[arr[i]] = count[arr[i]] + 1;
}
else
{
count.Add(arr[i], 1);
}
}
// Return the result
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 1, 2, 1, 1 };
int N = arr.Length;
// Function call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by PrinciRaj1992
输出：
3
时间复杂度：O(n)。
辅助空间：O(n)。
版权属于：月萌API www.moonapi.com，转载请注明出处
