共计 4620 个字符,预计需要花费 12 分钟才能阅读完成。
一、第一个缺失的整数
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; | |
} |