我是
靠谱客的博主
烂漫鞋垫，最近开发中收集的这篇文章主要介绍
找出数组中第一个重复的元素，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
给定一个整数数组，找到其中的第一个重复元素。我们需要找到多次出现的元素，并且它的第一次出现的索引最小。
例子：
输入：arr [] = {10,5,3,4,3,5,6}
输出：5 [5是重复的第一个元素]
输入：arr [] = {6,10,5,4,9,120,4,6,10}
输出：6 [6是重复的第一个元素]
我们可以使用排序来解决O（nLogn）时间内的问题。以下是详细步骤。
1）将给定数组复制到辅助数组temp []。
2）使用O（nLogn）时间排序算法对临时数组进行排序。
3）从左到右扫描输入阵列。对于每个元素，使用二分搜索在temp []中计算它的出现次数。一旦我们找到一个多次出现的元素，我们就会返回该元素。该步骤可以在O（nLogn）时间内完成。
我们可以使用Hashing平均在O（n）时间内解决这个问题。我们的想法是从右到左遍历给定的数组，并在我们找到右侧访问过的元素时更新最小索引。感谢Mohammad Shahid建议这个解决方案。
以下是这个想法的C ++和Java实现。
| /* C++ program to find first repeating element in arr[] */
#include<bits/stdc++.h>
using namespace std;
// This function prints the first repeating element in arr[]，此函数在arr []中打印第一个重复元素
void printFirstRepeating(int arr[], int n)
{
// Initialize index of first repeating element，初始化第一个重复元素的索引
int min = -1;
// Creates an empty hashset，创建一个空的hashset
set<int> myset;
// Traverse the input array from right to left，从右到左遍历输入数组
for (int i = n - 1; i >= 0; i--)
{
// If element is already in hash set, update min，如果元素已经在哈希集中，则更新min
if (myset.find(arr[i]) != myset.end())
min = i;
else // Else add element to hash set，否则将元素添加到哈希集
myset.insert(arr[i]);
}
// Print the result
if (min != -1)
cout << "The first repeating element is " << arr[min];
else
cout << "There are no repeating elements";
}
// Driver method to test above method
int main()
{
int arr[] = {10, 5, 3, 4, 3, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printFirstRepeating(arr, n);
}
//This article is contributed by Chhavi
//注释：set.find(xx)是返回xx这个数的迭代器，如果没有，就返回set.end()也就是最后一个元素的迭代器。 //set()的insert()和find()时间都是O(log n)外加层O(n)的循环，就是O(n logn) |
| /* Java program to find first repeating element in arr[] */
import java.util.*;
class Main
{
// This function prints the first repeating element in arr[]
static void printFirstRepeating(int arr[])
{
// Initialize index of first repeating element
int min = -1;
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Traverse the input array from right to left
for (int i=arr.length-1; i>=0; i--)
{
// If element is already in hash set, update min
if (set.contains(arr[i]))
min = i;
else // Else add element to hash set
set.add(arr[i]);
}
// Print the result
if (min != -1)
System.out.println("The first repeating element is " + arr[min]);
else
System.out.println("There are no repeating elements");
}
// Driver method to test above method
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {10, 5, 3, 4, 3, 5, 6};
printFirstRepeating(arr);
}
}
|
最后
以上就是烂漫鞋垫为你收集整理的找出数组中第一个重复的元素的全部内容，希望文章能够帮你解决找出数组中第一个重复的元素所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[LeetCode] 列表找唯一(元素或者序号)出处分析其它](/uploads/reation/bcimg8.png)
发表评论 取消回复