有个数组中有100w个数，其中有一个数重复了50w次，要求找出这个数字。

题目：有个数组中有100w个数，其中有一个数重复了50w次，要求找出这个数字。

60 个解决方案

#1

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

#2

ls正解

#3

引用 1 楼 six_dimensional 的回复:

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

表示支持！

#4

或者这样：先找出数组中三个不一样的数a，b，c去掉，然后每次对消两个不一样的数，以此循环，最终能得到我们要的数

#5

每次去掉两个不同的数，最后剩下来的就是要所要的数。

#6

ls的会得不到结果 因为正好是50w 不是50w+1

#7

引用 1 楼 six_dimensional 的回复:

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

是在说楼主的题目么。。。

#8

二分？

#9

楼上有几位比较搞笑，找到中位数对找重复了50w次的数有什么帮助？

#10

引用 9 楼 yingle2000 的回复:

楼上有几位比较搞笑，找到中位数对找重复了50w次的数有什么帮助？

重复了50w的数必然是第50w或50w+1小的数(假设这两个数都不是要找的数，最多只有50w-1个数重复，与题目不符)

#11

引用 9 楼 yingle2000 的回复:

楼上有几位比较搞笑，找到中位数对找重复了50w次的数有什么帮助？

因为重复了50w次，这个数肯定是第50w小 和/或 50w+1小的数

#12

引用楼主 heyangbin 的回复:

题目：有个数组中有100w个数，其中有一个数重复了50w次，要求找出这个数字。

先快速排序，然后枚举数组元素，碰到相同的数字就数它出现多少次，只到碰到跟它不一样的数字。如果有 N 个数字的话，排序 O(N log N)，最后枚举 O(N)。

#13

临时给你写了个更一般的程序，命令行输入输出。先输入数字个数，然后是数字，然后是要找的数字的出现次数。如果数组中存在这样一个数字，就会把它输出，否则输出 "Not Found"。如果这样的数字不止一个，那么输出第一个。

#include <iostream>
#include <algorithm>
using namespace std;

const int size_array = 1000000;
int a[size_array];

int compare(const void * x, const void * y)
{
	return *(int *)x - *(int *)y;
}

int main (int argc, char * const argv[]) {
    
	int num_elements;
	cout << "Please input the number of elements:" << endl;
	cin >> num_elements;

	cout << "Please input the elements:" << endl;
	for (int i = 0; i < num_elements; i++) {
		cin >> a[i];
	}

	qsort(a, num_elements, sizeof(int), compare);

	int frequency;
	cout << "Please input the number of occurences of the element to be found:" << endl;
	cin >> frequency;

	int i = 0;
	int count = 1;
	while (i < num_elements-1) {
		if (a[i] == a[i+1]) {
			while (a[i] == a[i+1] && i < num_elements-1) {
				count++;
				i++;
			}
			if (count == frequency) {
				cout << a[i-1] << endl;
				return 0;
			}
			count = 1;
		}else {
			i++;
		}
	}
	cout << "Not Found" << endl;
    return 0;

}

#14

引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。

这个不行的。因为恰好50组，都去掉了。。。

#15

引用 4 楼 six_dimensional 的回复:

或者这样：先找出数组中三个不一样的数a，b，c去掉，然后每次对消两个不一样的数，以此循环，最终能得到我们要的数

这个好像可以哎。。。威武

#16

引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。

这个才是正解~

#17

是道经典的题目.
做一个计数,如果遇到与之前一样的,那么计数加1，否则减一. 每当计数为0时,重新记录当前数字.

最终扫描结束记录的数字就是最多的那个.如果要判断是否超过1/2量，可以从头扫描一遍，数一数这个数字出现的次数。

#18

引用 16 楼 cilluick 的回复:

引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。


这个才是正解~

这样是不行的，因为有50w个相同的，如果恰好50w个和另外50w个其他数恰好两两分成一组，那岂不是所有数都抵消了吗？所以先要消去3个数，确保数组中相同的数占大半，然后才能两两对消，（两两比较，相同则留下来，不同的话则两个都消掉，如果最后剩下一个，那么剩下的一个就是我们要的数，如果最后剩下三个那么定有两个是一样的，他就是我们要求的数）

#19

我觉得这个题应该以概率的方式去解决，随机取出2个数，如果相同则记录该数字，如此取100个数字，分析这100个数字，如果大部分都相同，比如80个都是同一个数字，我们可认为这个数字就是重复50W次的。（具体概率我没有算）
但如果100W数字中50W个1，499999个2，1个3，这种数组的话只能做循环了，哪个数字的重复次数到50W就是哪个，没有好办法。

#20

应该是要找高效率的算法吧

#21

我在13楼的回帖都没有人看的么？

#22

重复了50w的数必然是第50w或50w+1小？？？？？？？？
我前面25w重复，最后25W重复呢？

#23

ls的没看清楚 这里是说排序后的情况

也就是说 第50w小和50w+1小

这题可以看成 无序数组求第50w小和50w+1小的数

#24

引用 21 楼 haow85 的回复:

我在13楼的回帖都没有人看的么？

因为有1/4楼的强人在

O(n)是最快的了
像ls说的50W个1，499999个2，1个3

#25

up这个

引用 18 楼 six_dimensional 的回复:

引用 16 楼 cilluick 的回复:
引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。


这个才是正解~

这样是不行的，因为有50w个相同的，如果恰好50w个和另外50w个其他数恰好两两分成一组，那岂不是所有数都抵消了吗？所以先要消去3个数，确保数组中相同的数占大半，然后才能两两对消，（两两比较，相同则留下来，不同的……

#26

引用 18 楼 six_dimensional 的回复:

引用 16 楼 cilluick 的回复:
引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。


这个才是正解~

这样是不行的，因为有50w个相同的，如果恰好50w个和另外50w个其他数恰好两两分成一组，那岂不是所有数都抵消了吗？所以先要消去3个数，确保数组中相同的数占大半，然后才能两两对消，（两两比较，相同则留下来，不同的话……

正解,V5

#27

  那个啥去掉两个不同的数  怎样去掉啊 用什么方法比较高效啦？？？

#28

引用 1 楼 six_dimensional 的回复:

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

这题的复杂度该分两部分吧,首先要先排序,然后找到第50w小和50w+1小的两个数,判断这两个数哪个是要找的数地最坏复杂度是 O(n) 

#29

引用 18 楼 six_dimensional 的回复:

引用 16 楼 cilluick 的回复:
引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。


这个才是正解~

这样是不行的，因为有50w个相同的，如果恰好50w个和另外50w个其他数恰好两两分成一组，那岂不是所有数都抵消了吗？所以先要消去3个数，确保数组中相同的数占大半，然后才能两两对消，（两两比较，相同则留下来，不同的话……

顶一个，也想多学习一下算法方面的知识。

#30

引用 1 楼 six_dimensional 的回复:

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

正解

#31

乱七八糟

LZ是找,50W个相同的数啊!

100W-50W+1,最多不相同的数

int* a=new int[100W];//100W个数在这
int* d=new int[50w+1];//所有不相同的数计数
int dn=0;//当前有多少个不相同的数
int i=0,j;
while(i<100W){
  j=0;
  while(j<dn){
    if(a[i]==d[j]){
      d[j]++;
      if(d[j]>=50W)//找到了
        goto end;
      break;
    }
  }
  //出现新的数
  if(j>=dn)
    d[j]=1;
  i++;
}
:end
printf(...d[j]);

#32

int* d=new int[50w+1];//所有不相同的数计数

改下

struct dd{
 int n;
 int count;//计数放这
};

//last 

free memory

#33

引用 1 楼 six_dimensional 的回复:

要找中位数，也就是第50w小和50w+1小的两个数，找任意第k小的数是很经典的分治法了，随便一本算法书上都有，最坏O（n）

不懂 哪个给我解释一下为什么

#34

引用 17 楼 qq120848369 的回复:

是道经典的题目.
做一个计数,如果遇到与之前一样的,那么计数加1，否则减一. 每当计数为0时,重新记录当前数字.

最终扫描结束记录的数字就是最多的那个.如果要判断是否超过1/2量，可以从头扫描一遍，数一数这个数字出现的次数。

+1
std::nth_element也可以。
qsort什么的在这里明显不实用。

#35

雷霆一下

#define 值 1000000
#define 最大值 //看你数值的类型
    int 数组[值];      
    int 排序组[最大值]={0};
    int 目标值 = 0;

    for(i=值;i>=0;--i){
       P[数组[i]] ++;
       目标值 = P[数组[i]]
       if(目标值 == 20000000){
           goto 标签_找到目标值了:
       }
    }
 

标签_找到目标值了:   

#36

引用 25 楼 ayw215 的回复:

up这个引用 18 楼 six_dimensional 的回复:

引用 16 楼 cilluick 的回复:
引用 5 楼 liao05050075 的回复:

每次去掉两个不同的数，最后剩下来的就是要所要的数。


这个才是正解~

这样是不行的，因为有50w个相同的，如果恰好50w个和另外50w个其他数恰好两两分成一组，那岂不是所有数都抵消了吗？所以先要消去3个数，确保……

正解。 差点我也误解了。。

#37

引用 24 楼 hai040 的回复:

引用 21 楼 haow85 的回复:
我在13楼的回帖都没有人看的么？

因为有1/4楼的强人在

O(n)是最快的了
像ls说的50W个1，499999个2，1个3

数据都是实数，也能到 O(n)？

#38

引用 35 楼 lwboss 的回复:

雷霆一下

C/C++ code

#define 值 1000000
#define 最大值 //看你数值的类型
    int 数组[值];      
    int 排序组[最大值]={0};
    int 目标值 = 0;

    for(i=值;i>=0;--i){
       P[数组[i]] ++;
       目标值 = P[数组[i]]
       if(目标……

你这个只能处理一定范围内的整数。

#39

引用 34 楼 frankhb1989 的回复:

引用 17 楼 qq120848369 的回复:

是道经典的题目.
做一个计数,如果遇到与之前一样的,那么计数加1，否则减一. 每当计数为0时,重新记录当前数字.

最终扫描结束记录的数字就是最多的那个.如果要判断是否超过1/2量，可以从头扫描一遍，数一数这个数字出现的次数。

+1
std::nth_element也可以。
qsort什么的在这里明显不实用。

楼主问的是出现频率为某个值的数字，不是第 n 大／小 元素。

#40

 LS发的那些代码我没看懂过... 谁能清楚的讲下这个题目该怎么求咯.

    什么  第50w小 和/或 50w+1小的数  这个有什么用??

#41

引用 40 楼 freshman_fantom_ywj 的回复:

 LS发的那些代码我没看懂过... 谁能清楚的讲下这个题目该怎么求咯.

    什么 第50w小 和/或 50w+1小的数 这个有什么用??

那个是他们误解了题目的意思，他们当成求第50w大／小的数字了。

#42

第一次循环
先找出数组中三个不一样的数a，b，c去掉

第二次循环
找出数组中两个不一样对消，

留下的就是你要找的数

#43

第50w小 和/或 50w+1小的数
是指这组数排序后，重复了50w次的这个数字的位置是集中在一起的。
这组排序后的数字的第50w 或 50w+1的位置上至少有一个是重复了50w次的数字，也就是题目的答案

#44

 两个对消  

int * pData   =数据开始地址;
int * pEnd = pData+1000000;
int * p1=pData   ;
int * p2=p1+1; 
while (p2<pEnd)
{
if (*p1!=*p2)//相同   两个数对消
{
p1++;
if (p1==p2)    
{
p1++;
p2++;
} 
}
else
  p2++;
}

   循环结果   if  p1>pData    你的数据中只有两个数，并且每个都50W个
              else    *p1就是你要找的数

#45

上面写错，纠正一下

循环结果 if p1>pEnd 你的数据中只有两个数，并且每个都50W个
  else *p1就是你要找的数

#46

引用 43 楼 studyall123 的回复:

第50w小 和/或 50w+1小的数
是指这组数排序后，重复了50w次的这个数字的位置是集中在一起的。
这组排序后的数字的第50w 或 50w+1的位置上至少有一个是重复了50w次的数字，也就是题目的答案

我晕，排序就已经 O(N log N) 了。然后再扫描一遍数组就可以了啊。就是我在13楼给的答案啊。

#47

引用 10 楼 kingstarer 的回复:

引用 9 楼 yingle2000 的回复:
楼上有几位比较搞笑，找到中位数对找重复了50w次的数有什么帮助？


重复了50w的数必然是第50w或50w+1小的数(假设这两个数都不是要找的数，最多只有50w-1个数重复，与题目不符)

引用 11 楼 xskzzk 的回复:

引用 9 楼 yingle2000 的回复:
楼上有几位比较搞笑，找到中位数对找重复了50w次的数有什么帮助？


因为重复了50w次，这个数肯定是第50w小 和/或 50w+1小的数

我把中位数与中值搞错了。。。

#48

该回复于2010-09-13 09:57:01被版主删除

#49

我初学c++~ 底子很薄，上面的东东，看的不是太懂，但是给我不少启发，我试过先排序，但是我发现一百万这个庞大的数字无论是插入，冒泡，还是选择所需的时间都是很长，自己写了个小方法，时间太晚了就没写注释，明天还得上学呢~  有什么毛病大家多指教啊·
void search(int*&p)
{   
int i,j;
int sum = 0;
for(i=0;i<500000;i++)
{

for(int j=0;j<1000000;j++)
{
if(*(p+i)==*(p+j))
{
                 sum++; 
}

    }
   if(sum==500000)
{
        
                goto LOOP;
}
else
{

sum = 0;
   }
}
LOOP:  
 cout<<"搜寻的数字是>>>>"<<*(p+i)<<"<<<<"<<endl;
} 

#50

对了 好心人能讲讲那个 什么 50w 和50w+1 是这么回事么  ··· 期待·~