一、第一个缺失的整数
1. 题目
给定一个数组A[0…N-1]，找到从 1 开始，第一个不在数组中的正整数。
如给定 3,5,1,2,-3,7,14,8，输出 4。
2. 分析
针对这道题目，有两种思路。
第一种思路是基于 bitmap 思想，开辟一个新数组 B[0 .. N-1]，数组元素全部初始化为0，遍历一次 A 数组，若遍历到的元素其值为在0 与N-1之间的正整数 i，则在 B 数组中将对应下标i 的元素 B[i] 设为 1，最后遍历 B 数组，找到第一个值为0 的元素，其下标就是需要找的第一个不在数组中的正整数。
此方法时间复杂度为O(N)，空间复杂度为O(N)。
若允许修改原数组，便可以引出第二种思路即循环不变式原理。
此算法时间复杂度为O(N)，空间复杂度为O(1)。
3. 代码
int first_miss_number(int a[], int n){
a--; // 使 a 从 1 开始数
int i = 1;
while(i<=n){if(a[i] == i) i++;
else if(a[i]<i || a[i]>n || a[i]==a[a[i]])
a[i] = a[n--];
else // a[i]>i
swap(a[a[i]], a[i]);
}
return i;
}二、查找旋转数组的最小值
1. 题目
假定一个排序数组以某个未知元素为支点做了旋转，如：原数组 0 1 2 4 5 6 7 旋转后得到4 5 6 7 0 1 2。请找出旋转后数组的最小值。(假定数组中没有重复数字)
2. 分析
旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素；
4 5 6 7 0 1 2
注意到实际上最小的元素就是两个子数组的分界线。
可以看到，算法的思想与二分搜索比较类似，时间复杂度为 O(logN)，比遍历一遍数组得到最小值的方法要快。
3. 代码
int find_min(int a[], int n){
int low = 0;
int high = n - 1;
int mid;
while(low<high){mid = (high + low) / 2; // 需注意，若数组过大，此项可能会造成溢出
if(a[mid]<a[high]) // 最小值在左半部分
high = mid;
else // 最小值在右半部分
low = mid + 1;
}
return a[low];
}三、零子数组
1. 题目
求对于长度为 N 的数组 A，求连续子数组的和最接近 0 的值。
如：数组 A、1, -2, 3, 10, -4, 7, 2, -5，它的所有子数组中和最接近 0 的是哪个？
答案是 -4, 7, 2, -5，其和正好是 0。
2. 分析
(1) 申请比 A 长 1 的空间 sum[-1,0…,N-1]，sum[i] 是 A 的前 i 项和。(trick：定义 sum[-1] = 0)
显然有：
(2) 对 sum[-1,0…,N-1] 排序，然后计算 sum 相邻元素的差的绝对值，最小值即为所求。
计算前 n 项和数组 sum 和计算 sum 相邻元素差的时间复杂度，都是 O(N)，排序的时间复杂度认为是 O(NlogN)，因此，总时间复杂度为 O(NlogN)。
思考：如果需要返回绝对值最小的子数组本身呢？
此时可以引入结构体，其中包含两个成员 sum 和 pos，分别表示前 i 项和 sum 和该位置 pos，即 pos=i。然后对该结构体根据 sum 值进行排序，取满足相邻元素的差的绝对值的两个结构体的 pos 的值，然后根据两个 pos 值在数组中输出对应元素，即为所求零和数组。
3. 代码
typedef struct{
int sum;
int pos;
}SUM;
/**
* 求零和数组
* 返回最接近 0 的值, low 为零和数组第一个元素的前一个位置下标, high 为零和数组最后一个元素的下标
*/
int zero_subarray(int a[], int n, int &low, int &high){SUM b[n];
b[0].sum = a[0];
b[0].pos = 0;
for(int i=1; i<n; i++){b[i].sum = b[i-1].sum + a[i];
b[i].pos = i;
}
cout<<"排序前："; print_sum(b, n);
// 排序 (此处省略排序的实现细节)
sum_sort(b, n);
cout<<"排序后："; print_sum(b, n);
// 计算差值最小的两个 sum
int diff, result = b[1].sum - b[0].sum;
low = min(b[0].pos, b[1].pos);
high = max(b[0].pos, b[1].pos);
for(int i=1; i<n; i++){diff = abs(b[i].sum - b[i-1].sum);
if(diff < result){ // 更新
result = diff;
low = min(b[i].pos, b[i-1].pos);
high = max(b[i].pos, b[i-1].pos);
}
}
return result;
}
/**
* 打印零和数组
*/
void print_zero_subarray(int a[], int n, int low, int high){
int i;
for(i=low+1; i<high; i++)
cout<<a[i]<<",";
cout<<a[i]<<endl;
}
/**
* 打印 SUM 结构体数组
*/
void print_sum(SUM *b, int n){
int i=0;
for(i=0; i<n-1; i++)
cout<<"("<<b[i].sum<<","<<b[i].pos<<"),";
cout<<"("<<b[i].sum<<","<<b[i].pos<<")"<<endl;
}
/**
* 主函数
*/
int main(){int a[] = {1,-2,3,10,-4,7,2,-5};
int n = 8;
int low, high;
cout<<"最接近 0 的和："<<zero_subarray(a, n, low, high)<<endl;
cout<<"零和数组为：";
print_zero_subarray(a,n,low,high);
return 0;
}输出结果为：
排序前：(1,0), (-1,1), (2,2), (12,3), (8,4), (15,5), (17,6), (12,7)
排序后：(-1,1), (1,0), (2,2), (8,4), (12,3), (12,7), (15,5), (17,6)
最接近 0 的和：0
零和数组为：-4,7,2,-5
四、最大子数组和
1. 题目
给定一个数组 A[0,…,n-1]，求 A 的连续子数组，使得该子数组的和最大。
例如:
数组：1, -2, 3, 10, -4, 7, 2, -5，
最大子数组：3, 10, -4, 7, 2
最大子数组和：18
2. 分析与代码
本题可以利用动态规划 (最优子问题) 的思路来求解，时间复杂度为 O(N)，算法步骤如下：
记 S[i]为以 A[i]结尾的数组中和最大的子数组，则：
- 令 result 初始化为 A[0]，S[0] = A[0]
- 在 i 的范围 [1，n) 中遍历 i，若 S[i-1] > 0，则 S[i] = S[i-1] + A[i]
- 若 S[i-1] <= 0，则 S[i] = A[i]
- 此时的最大子数组和为：result = max(result, S[i])
代码如下：
/**
* 求解最大子数组和
*/
int max_subarray(const int a[], int n){if(!a || n<=0) return 0;
int sum = a[0];
int result = sum; // 记录当前最优解
for(int i=1; i<n; i++){if(sum>0) sum+=a[i];
else sum = a[i];
result = max(sum, result);
}
return result;
}思考：若除了输出最大子数组的和，还需要输出最大子数组本身，应该怎么做？
此时可以设置两个标志 from 和 to 来表示最大子数组的起点和终点，
记 sum 没为以 A[i]结尾的数组中的最大子数组和，则：
- 令 result 初始化为 A[0]，sum = A[0], from = to = -1，- 1 表示无元素
- 在 i 的范围 [1，n) 中遍历 i，若 sum > 0，则 sum = sum + A[i]
- 若 sum <= 0，则 sum = A[i]，记录 from_new = i
- 此时进行判断，若 result < sum，即当前 sum 的值为最优解，更新起点 from 和终点 to，from = from_new，to = i，
输出数组 A[n]从 from 到 to 的元素，即为最大子数组。
代码如下：
/**
* 求解最大子数组和及最大子数组本身
*/
int max_subarray_pos(const int a[], int n, int &from, int &to){if(!a || n<=0){
from = to = -1;
return 0;
}
int sum = a[0];
int result = sum; // 记录当前最优解
from = to = 0;
int from_new; // 新的子数组起点
for(int i=1; i<n; i++){if(sum>0) sum+=a[i];
else{ // 最大子数组的起点发生了改变
sum = a[i];
from_new = i;
}
if(result < sum){
// 当前的最大和大于 result，将最优解的起点 from 改变到 from_new，结束点 to 改变到 i
result = sum;
from = from_new;
to = i;
}
}
return result;
}
// 输出最大子数组代码
for(i=from; i<to; i++)
cout<<a[i]<<",";
cout<<a[i]<<endl;五、最大间隔
1. 题目
给定整数数组 A[0…N-1]，求这 N 个数排序后的最大间隔。
如：1,7,14,9,4,13 的最大间隔为 4。
排序后：1,4,7,9,13,14，最大间隔是 13-9=4
显然，对原数组排序，然后求后项减前项的最大值，即为解，时间复杂度为 O(nlogn)。可否有更好的方法？
（若将题中条件整数数组改为浮点数组，题目会变得更简单，注意：是变得更简单，为什么？）
2. 分析
本解法的时间复杂度为 O(n)。
(也由上可知，若题干条件换成浮点数组，题目会变得更好计算桶的数目和大小，以及分配数组元素)
3. 代码
/**
* 桶
*/
typedef struct Bucket{
bool isEmpty;
int min;
int max;
Bucket() : isEmpty(true) {}
void add(int k){if(isEmpty){
min = max = k;
isEmpty = false;
} else{if(max < k) max = k;
if(min > k) min = k;
}
}
}Bucket;
/**
* 计算最大间距
*/
int calc_max_gap(const int a[], int n){Bucket bucket[n];
// 计算数组 a 的最值
int max = a[0], min = a[0], i;
for(i=0; i<n; i++){if(max < a[i]) max = a[i];
if(min > a[i]) min = a[i];
}
// 将数据依次放入桶中
int delta = max - min;
int num; // 标记该数应该在哪一个桶里
for(i=0; i<n; i++){num = (a[i] - min) * n / delta;
if(num >= n) num = n-1;
bucket[num].add(a[i]);
}
// 计算有效桶
i = 0;
int gap = delta / n; // 初始化最小间隔为桶的间距
int t;
for(int j=1; j<n; j++){ // i 为前一个桶，j 为后一个桶
if(!bucket[j].isEmpty){ // 桶不空
t = bucket[j].min - bucket[i].max;
gap = gap > t ? gap : t;
i = j;
}
}
return gap;
}