const int SIZE = 1 << 14;
char getc() {
static char buf[SIZE], *begin = buf, *end = buf;
if (begin == end) {
begin = buf;
end = buf + fread(buf, 1, SIZE, stdin);
}
return *begin++;
}
int read() {
int sgn = 0, ret = 0, ch = getc();
while (!isdigit(ch) && ch != EOF) ch |= ch == '-', ch = getc();
while (isdigit(ch) && ch != EOF) ret = ret * 10 + ch - '0', ch = getc();
return sgn ? -ret : ret;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
这段代码在
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
的条件（即文件输入输出）中能否运行正常？
可以的
这个时候，上面的方法就不行了，因为在遍历到最后一个数字时，times = 0,这个时候我们需要最后一个数，但是数组已经遍历完毕，保存可能是前面的某一个数。
如0,1,2,1
i = 0 ,result =0,times = 1;
i = 1，a[1]!= result;times–;times = 0;
i = 2 ,result = 2;times = 1;
i = 3,a[3] != result,times–;times = 0;
输出result = 2;但是我们需要时返回2的下一个数1。
如果是0,2,1,1
i = 0;result = 0;times= 1;
i = 1,a[1] != result ;times–;times= 0;
i = 2,result = 1,times = 1;
i = 3,a[3] == result;times++;times = 2;
输出result = 1;
我们会发现，实际上我们要判断的就是遍历到最后的时候保存的result和最后一个元素的比较，最后的输出从两个数之间选出。
我们可以针对最后一个元素，声明一个变量ntimes,遍历数组时，判断如果当前元素等于最后的元素，ntimes次数加一,最后直接判断，ntimes == N/2 ,如果true,说明最后一个元素就是，如果false，说明result中保存的数就是要找的。
int Find2(int * data,int length)
{
int result,times,ntimes;
times = ntimes = 0;
int i;
for(i = 0;i<length;i++)
{
if(data[i] == data[length-1])
ntimes++; //最后一个元素出现次数
if(times== 0)
{
result = data[i];
times = 1;
}
else
{
if(data[i] == result)
times++;
else
times--;
}
}
if(ntimes*2 == length)
return data[length-1];
else
return result;
}