一、第一个缺失的整数

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;
}