问题描述：一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
思路：如果能用两个辅助数组，那么相对来说简单一点，可定义数组Min和数组Max，其中Min[i]表示自a[i]之后的最小值（包括a[i]），Max[i]表示自a[i]之前元素的最大值。有了这两个辅助数组后，对于a[i]，如果它大于Max[i-1]并且小于Min[i+1]，那么就符合要求。
但是题目要求是只用一个额外数组，其实Max数组可以省去，完全可以边判断边计算，这是因为Max[i]是自左往右计算的，而判断时也是自左往右，两个过程正好可以合起来。只需用一个变量Max保存一下当前的最大值即可。下面给出两种方法的代码实现。
参考代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
//函数功能 ： 找元素 //函数参数 ： pArray指向数组，len为数组的元素个数 //返回值 ： 无 void FindElements_Solution1(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int *pMax = new int[len]; int i; pMax[0] = pArray[0]; for(i = 1; i < len; i++) //计算自i往前最大值的辅助数组 pMax[i] = (pMax[i-1] >= pArray[i])? pMax[i-1]: pArray[i]; pMin[len-1] = pArray[len-1]; for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组 pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; if(pArray[0] <= pMin[0]) //检查第1个元素是否满足条件 cout<<pArray[0]<<' '; for(i = 1; i < len - 1; i++) { if(pArray[i] >= pMax[i-1] && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求 cout<<pArray[i]<<' '; } if(pArray[len-1] >= pMax[len-1]) //检查第len个元素是否满足条件 cout<<pArray[i]; cout<<endl; delete [] pMin; delete [] pMax; pMin = pMax = NULL; } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
void FindElements_Solution2(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int Max; int i; Max = pArray[0]; pMin[len-1] = pArray[len-1]; for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组 pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; if(pArray[0] <= pMin[0]) //检查第1个元素是否满足条件 cout<<pArray[0]<<' '; for(i = 1; i < len - 1; i++) { if(pArray[i] >= Max && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求 cout<<pArray[i]<<' '; Max = (Max < pArray[i])? pArray[i]: Max; //更新当前最大值 } if(pArray[len-1] >= Max) //检查第len个元素是否满足条件 cout<<pArray[i]; cout<<endl; delete [] pMin; pMin = NULL; } |
找出数组中两个只出现一次的数字（数组）
问题描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
思路：如果只有一个数字只出现一次，而其他都出现两次，则直接将所有数字做一次异或运算即可，因为相等的数字异或一下结果为0。如果有两个数字只出现一次，而其他数字出现了两次。该怎么办呢？《编程之美》一书提供了一种方法，即先将所有数字做一次异或运算，得到一个数字，然后以该数字的某非0位作为过滤位，将数组分成两个部分，此时只出现一次的数字会被分到不同的部分。现在问题就转为只出现一次的情况，对每部分分别做异或运算即可。
参考代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//函数功能 ： 找出数组中两个只出现一次的数字 //函数参数 ： arr为源数组，len为数组元素个数，result用来存放结果 //返回值 ： 无 void FindIsolateTwo(int *arr, int len, int *result) { int i, all = 0, flag = 1; for(i = 0; i < len ; i++) //所有数异或 all ^= arr[i]; while(!(all&flag)) //寻找过滤位 flag <<= 1; result[0] = result[1] = 0; for(i = 0; i < len; i++) //利用过滤位区分 { if(flag&arr[i]) result[0] ^= arr[i]; else result[1] ^= arr[i]; } } |
