Mayuyu最近遇到了一些很有趣的题目，现在就来和大家一起分享。。。
题目：给定一个升序数组，如何在这个数组中快速找出两个数，其和等于一个给定的值。
分析：对于本问题最直观的想法就是枚举一个数找另一个数，这样时间复杂度为O(n^2)。嗯，不是我们想要的，需
要寻求更高级的算法。既然这个数组是有序的，实际上我们可以这样做，在这个数组的头尾设置两个指针，假
设分别是i和j，从两端分别向中间走，如果出现a[i] + a[j] < sum，那么说明a[i]偏小，所以把i++，
如果出现a[i] + a[j] > sum，那么说明a[j]偏大，相应的j--，可以看出这样时间复杂度为O(n)。
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N = 100005;
int a[N];
int index1,index2;
void Find(int a[],int n,int sum)
{
int i = 0;
int j = n - 1;
while(i < j)
{
if(a[i] + a[j] == sum)
{
index1 = i;
index2 = j;
break;
}
else if(a[i] + a[j] < sum) i++;
else j--;
}
}
int main()
{
int n,sum;
while(cin>>n>>sum)
{
index1 = index2 = -1;
for(int i=0;i<n;i++)
cin>>a[i];
Find(a,n,sum);
cout<<index1<<" "<<index2<<endl;
}
return 0;
}
题目：有一个名人和很多平民在一块，平民都认识这个名人，但是这个名人不认识任何一个平民，任意两个平民之
间是否认识是未知的，请设计一个算法，快速找个这个人中的那个名人。
已知已经实现了一个函数bool know(int a,int b) 这个函数返回true的时候，表明a认识b，返回
false的时候表明a不认识b。
思路：首先将n个人分为n/2组，每一组有2个人，然后每个组的两个人调用know函数，假设为know(a,b)，返
回true的时候说明a认识b，则a肯定不是名人，a可以排除掉了，依次类推，每个组都调用这个函数依次，
那么n个人中就有n/2个人被排除掉了，数据规模将为n/2。同理在剩下的n/2个人中在使用这个方法，那
么规模就会将为n/4，这样总的遍历次数为n/2+n/4+n/8+... 这是一个等比数列，时间复杂度为O(n)。
题目：如何判断一个自然数是否是某个数的平方，不使用开根号函数。
分析：这个问题实际上，我们可以通过二分查找来计算，时间复杂度为log(n)。实际上还有一种方法，因为我们
知道
终为0，说明这个数是一个完全平方数，否则不是。
bool isSqrt(int n)
{
int i = 1;
n -= i;
while(n > 0)
{
i += 2;
n -= i;
}
if(n == 0)
return true;
else
return false;
}
题目：1~N的数字，其中有一个数字出现了两次，所以一共是N+1个数字。现在要求找出唯一出现过两次的数字。不
使用辅助存储空间。
分析：这个题很简单啦，因为我们知道两个相同的数字异或后得到0，那么我们先对1~N的所有数字异或，然后再对
所有的a[i]异或即可。
int Find(int a[],int n)
{
int ans = 0;
for(int i=1;i<=n;i++)
ans ^= i;
for(int i=0;i<=n;i++)
ans ^= a[i];
return ans;
}
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：其实这个问题有3种比较好的方法
（1）一边扫描，相当于每次消去2个不同的元素，最后剩下的肯定是要找的元素
（2）利用哈希表或者数组统计每个字符出现的次数，然后从里面找到出现次数超过一半的
（3）排序后，取数组的中间元素
题目：找到单向链表中间那个元素，如果有两个则取前面一个。
分析：
方法一：两遍扫描。第一遍，找到长度，然后算出中间值；第二遍，定位中间值。
方法二：一遍扫描。用两个指针，一个步长为1，一个步长为2，当步长2的那个指针走到头时，这个时候步长为1的
那个指针刚好指着中间的那个结点。
题目：50亿个32位的整数，如何找出重复出现的元素。
分析：利用位图记录即可，大约用512MB的空间。
题目：1亿个数找出最小的1万个数。
分析：（1）简历最大堆，询问即可
（2）利用部分快速排序，时间复杂度约为O(n)
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int N = 100005;
int a[N];
int partion(int a[],int L,int R)
{
int key = a[R];
int i = L - 1;
for(int j=L;j<R;j++)
{
if(a[j] < key)
{
swap(a[i+1],a[j]);
i++;
}
}
int tmp = a[i+1];
a[i+1] = key;
a[R] = tmp;
return i + 1;
}
void QuickSort(int a[],int L,int R,int k)
{
if(L < R)
{
int p = partion(a,L,R);
int len = p - L + 1;
if(len == k) return;
if(len < k)
QuickSort(a,p+1,R,k-len);
else
QuickSort(a,L,p-1,k);
}
}
int main()
{
int n,k;
while(cin>>n>>k)
{
for(int i=0; i<n; i++)
cin>>a[i];
QuickSort(a,0,n-1,k);
for(int i=0; i<k; i++)
cout<<a[i]<<endl;
}
return 0;
}
原文：http://blog.csdn.net/achelloworld/article/details/23201535