在一个A
大小的数组中2N
,有N+1
独特的元素,这些元素中的一个重复N次。
返回重复N次的元素。
例1:
输入:[1,2,3,3]
输出:3
例2:
输入:[2,1,2,5,3,2]
输出:2
例3:
输入:[5,1,5,2,5,3,5,4]
输出:5
解法一:
题目中可以得知数组大小i为2N,有N+1个独特的元素(即不存在重复的元素N+1个),所以仅仅只有那个重复N次的元素在数组中有多个,其他元素在数组中仅出现一次
两次for循环,暴力解法
public int repeatedNTimes(int[] A) {
int N=A.length/2;
int temp=0;
for (int i=0;i<A.length;i++)
{
for (int j=i+1;j<A.length;j++)
{
if (A[i]==A[j])
{
temp=A[i];
break;
} }
}
return temp;
} 解法2:通过桶排序。初始化一个足够大的数组B,A数组中的值跟B数组中的下标对应,B数组中的值代表A数组元素出现的的次数。通过for循环,循环A中元素,A中元素重复则A元素作为B数组下标对应数组值+1
public static int repeatedNTimes(int[] A) {
int temp=0;
int B[]=new int[10000];
for (int i=0;i<A.length;i++)
{
B[A[i]]++;
if (B[A[i]]>1)
{
temp=A[i];
}
}
return temp;
}