1.找出数组中唯一的重复元素
问题描述：给定包含101个元素的数组arr，数组中元素一定属于[1，100]，并且[1，100]之间的每个数都在arr中出现过。
解决方案：分析，数组中有101个元素，如果[1，100]之间的每个数出现一次，那就是100个元素了，剩下的那个元素就是唯一的重复出现的元素。我们可以通过遍历arr，得到arr中所有元素的总和，然后既然[1，100]之间的每个数出现一次，那么我们减去1+2+……+99+100的和，结果就是我们需要的唯一的重复出现的元素了。时间复杂度是O(n)。
代码：
1 //找到数组中唯一的重复元素
2 int FindOnlyRepeat(int *arr)
3 {
4 int tmp_sum = 0;//记录1~100的和
5 int total_sum = 0;//数组中所有树的和
6 int i = 0;
7 while(i < 101)
8 {
9 tmp_sum += i+1;
10 total_sum += arr[i++];
11 }
12 tmp_sum-=101;
13 return total_sum - tmp_sum;
14 }
2.找出数组中出现奇数次的元素
问题描述：现在有一个整数数组arr，其中的元素只有一个元素出现奇数次，请找出这个元素。
解决方案：对于任意一个数k，有k^k = 0，k^0 = k，所以将arr中所有元素进行异或，那么出现次数为偶数的元素异或后都变成了0，出现次数为奇数的元素异或后得到元素本身。下面写代码就很容易了~~时间复杂度是O(n)。
代码：
1 //找出数组唯一的出现次数是奇数的元素
2 int Find(int *arr,int n)
3 {
4 int ans = arr[0];
5 for(int i = 1 ; i < n ; i++)
6 {
7 ans^=arr[i];
8 }
9 return ans;
10 }
3.找出两个数组中满足给定和的数对
问题描述：有两个数组arr1和arr2，两个数组均已经排好序，现在要找出这样的x和y使得x+y=sum，其中sum已知，x是arr1中某个元素，y是arr2中的某个元素。
解决方案：既然数组arr1和arr2中的元素已经排好序了，那么问题就简单了不少。假设arr1[i] + arr2[j] > sum，若arr1下标不变，那么要找到满足条件的x和y，只能取arr2中下标< j 的元素和arr1[i]相加，结果才可能等于sum；假设arr1[i] + arr2[j] < sum，若arr2的下标不变，那么要找到满足条件的x和y，只能取arr1中下标 > i 的元素和arr2[j]相加，结果才可能等于sum。因此我们可以设置两个指针 i 和 j ，分别指向arr1的开始位置和结束位置，这时 i 只能不断变大，j 只能不断变小，直到超过了数组的范围。通过代码更好理解，看代码吧~~时间复杂度是O(n+m)，n和m分别是arr1和arr2的大小。
代码：
1 //找出数组中两个数的和是固定值
2 void FindTheSum(int *arr1,int *arr2,int n,int m,int sum)
3 {
4 int i = 0 , j = m-1;
5 while(i < n && j >= 0)
6 {
7 if(arr1[i] + arr2[j] > sum)
8 {
9 j--;
10 }
11 else if(arr1[i] + arr2[j] < sum)
12 {
13 i++;
14 }
15 else
16 {
17 cout<<arr1[i]<<" + "<<arr2[j]<<" = "<<sum<<endl;
18 i++;
19 j--;
20 }
21 }
22 }
4.最大子段和
问题描述：对于整数数组arr，求出最大连续子段之和，字段和是这样的： i 和 j 是数组下标并且i <= j ，那么sub_sum = arr[i] + arr[i+1]……+arr[j]，就是一段子段和，我们的目的是找到最大的子段和。如果和为负数，按0计算。
解决方案：这个算法，可是算得上是比较经典的算法了，对照着代码，理解一下思路吧：MAX是记录在搜索过程中出现的最大值，也就是最终的最大值保存的地方，而对于tmp的话，tmp > 0，就说明如果tmp继续和后面的数（假设是arr[i]）相加，就能继续使得以a[i]结尾的子段和变大，而当tmp < 0 ，就说明这个值不能加到a[i]上，这一定会导致总和不是最大的，tmp的意图比较像是获得“最大前缀和”！！我就说这么多吧，这个东西还是看代码理解吧！！时间复杂度是O(n)。
代码：
//求最大子段和
2 int MaxSubSum(int *arr,int n)
3 {
4 int tmp = 0;
5 int MAX = arr[0];
6 for(int i = 0 ; i < n ; i++)
7 {
8 tmp += arr[i];
9 if(tmp < 0)
10 {
11 tmp = 0;
12 }
13 if(MAX < tmp)
14 {
15 MAX = tmp;
16 }
17 }
18 return MAX;
19 }
5.最大子段积
问题描述：对于整数数组arr，求出最大连续子段积。具体什么是最大连续子段积，我想参考最大字段和应该能知道。
解决方案：和最大子段和的思想和很相似，看代码！时间复杂度是O(n)
代码：
1 int MaxSubMult(int *arr,int n)
2 {
3 int min_Mult = 1;
4 int max_Mult = 1;
5 int ans = arr[0];
6 for(int i = 0 ; i < n ; i++)
7 {
8 if(arr[i] > 0)
9 {
10 max_Mult *= arr[i];
11 min_Mult = min_Mult*arr[i] < 1 ? min_Mult*arr[i] : 1;
12 }
13 else if(arr[i] < 0)
14 {
15 int tmp = max_Mult;
16 max_Mult = min_Mult*arr[i] > 1 ? min_Mult*arr[i] : 1;
17 min_Mult = tmp*arr[i];
18 }
19 else //arr[i] = 0
20 {
21 max_Mult = 1;
22 min_Mult = 1;
23 }
24 if(max_Mult > ans)
25 {
26 ans = max_Mult;
27 }
28 }
29 return ans;
30 }
6.一种特殊的排序（重排问题）
问题描述： 对于整数数组arr中包含0和非0元素，现在要对数组进行处理，使得处理后的结果满足：（1）0都排在数组的前面（2）非0元素都在数组的后面，并且相对顺序不能变化。例如arr[] = {3,0,1,0}，经处理后的结果应为：{0,0,3,1}。
解决方案：要完成这个要求，只需要从后向前遍历数组arr，遇到一个非0的数就将其放到数组的后面，遇到的第一个非0元素放在数组的第n-1位置，遇到的第二个非0元素放在数组的第n-2位置（其中n是数组的大小）。这样就完成了题目的要求！！！时间复杂度是O(n)
代码：
void Deal(int *arr,int n)
2 {
3 int tmp = n-1;
4 for(int i = n-1 ; i >= 0 ; i--)
5 {
6 if(arr[i])
7 {
8 if(!arr[tmp])
9 {
10 arr[tmp] = arr[i];
11 arr[i] = 0;
12 }
13 tmp--;
14 }
15 }
16 }
7.找出绝对值最小的数
问题描述：整数数组arr已经排好序，其中包含正数，0负数，数组大小是n，要求找到绝对值最小的数。
解决方案：通过分析有几种情况：（1）若arr[0]和arr[n-1]同号且arr[0]>=0，则绝对值最小的数是arr[0];（2）若arr[0]和arr[n-1]同号且arr[0]<=0，则绝对值最小的数是arr[n-1];（3）若arr[0]和arr[n-1]不同号，则绝对值最小数应该是“最小的正整数”和“最大的负整数”中的一个。关键就是找到这“最小的正整数”和“最大的负整数”。既然数组是已经排好序了，那么可以利用二分。
代码：
1 int MinAbs(int *arr, int n) 2 { 3 if(n == 1) //只有一个元素 4 { 5 return arr[0] ; 6 } 7 if(arr[0]*arr[n-1] >= 0) 8 { 9 return arr[0] >=0 ? arr[0] : arr[n -1] ; 10 } 11 int l =0 ; 12 int r = n - 1; 13 while(l < r) 14 { 15 cout<<l<<" "<<r<<endl; 16 if(l + 1 == r)//出口，只剩下两个元素，可以得到结果了 17 { 18 return abs(arr[l]) < abs(arr[r]) ? abs(arr[l]) : abs(arr[r]); 19 } 20 int m = (l + r) / 2; 21 if(arr[m] * arr[r] >= 0) 22 { 23 r = m; 24 continue; 25 } 26 if(arr[l] * arr[m] >= 0) 27 { 28 l = m; 29 continue; 30 } 31 } 32 }
参考资料：
【1】博文http://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html#link13
【2】《编程之美》