ch6 - 数组 Array
**数组大部分的题目是偏算法的，这部分主要讲以下两类数组问题：
- Sorted Array - 排序数组
- Subarray - 子数组**
目录：
- Merge Two Sorted Arrays（6 in lintcode）(★★★★★)
- Median of Two Sorted Arrays（65 in lintcode）(比较难★★★★★) quick select
- Maximum Subarray（41 in lintcode）
- Subarray Sum （138 in lintcode）
- Subarray Sum Closest （139 in lintcode）
第一部分：Sorted Array - 排序数组
1. Merge Two Sorted Arrays（6 in lintcode）(★★★★★)
1.1求解步骤
step 1：新开辟一个放最终结果的数组，有三个指针i，j，k，分别指向A、B、C数组的下标；
step 2：i，j指向的数比较大小，将较小的数放入新数组，修改i，j指针；
step 3：将A或B剩余部分放入新数组。
1.2 代码
class Solution {
public:
/*
* @param A: sorted integer array A
* @param B: sorted integer array B
* @return: A new sorted integer array
*/
vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
// write your code here
if(A.size()==0){
return B;
}
else if(B.size()==0){
return A;
}
vector<int> res(A.size()+B.size(),0);
int i = 0, j = 0, k = 0;
while(i<A.size() && j<B.size()){
if(A[i] < B[j]){
res[k++] = A[i++];
}
else{
res[k++] = B[j++];
}
}
while(i<A.size()){
res[k++] = A[i++];
}
while(j<B.size()){
res[k++] = B[j++];
}
return res;
}
};
1.3 该问题很简单，但是有很多follow up
1.3.1 follow up1:将有序小数组归并到有序大数组里，大数组中空间足够大
1).题目链接
• http://www.lintcode.com/problem/merge-sorted-array/
• http://www.jiuzhang.com/solutions/merge-sorted-array/
2).时间复杂度 O(m+n)
从末尾开始向开头归并
1.3.2 follow up2: 两个数组的交
0). 题目链接
• http://www.lintcode.com/problem/intersection-of-two-arrays/
num1 = [1,2,2,1]，num2 = [2,2]， return [2]
不止一种做法，面试官希望你提出多种做法，并比较时间复杂度。
1). 方法1：quick sort + merge
先排序，后merge，merge时碰到相同的则放入结果数组。
time：O(nlogn + mlogm + n + m) = O(nlogn + mlogm)
space：O(1)
2). 方法2：hashSet
先将一个数组丢到hashSet中，在判断另一个数组中的数是不是在hashSet中。
time：O( n + m)
space：O( min（n，m）)
3). 方法3：binary search
用二分法查询一个数是否在一个有序数组中。所以先对比较小的数组进行排序，然后用二分法依次判断大数组中的每个数是否在小数组中。
如果n<m
time：O(nlogn + mlogn) = O( (n+m)logn )
space：O(1)
4). 方法比较：
！！！ hashSet和binary search 都是解决一个数是不是在一个集合中。
方法1比方法3稍微差一点，但是方法2和3不能直接比较。
方法1，3破坏了原数组，即破坏了输入，但方法2占用了额外空间。
1.3.3 follow up3: 数组内积（点乘）
Example [1,3] · [2,4] = 12 + 34 = 14
Follow up: 两个数组都非常大，但是其中都包含很多0
Example [1,0,0,0,0 …, 0, 2, 0,…, 0, 3] · [0,…, 0, 4, 0,…, 0, 5]
这个题和AI是有关系的，本质就是向量相乘。本题更像一个设计题，用<pos，val>存数组。如：
num1 = [<0,1>, <100,1>, <1000,1>]
num2 = [<5,1000>, <100,1>, <999,1>]
2. Median of Two Sorted Arrays（65 in lintcode）(比较难★★★★★)
2.1 题目描述
A = [1,3,5]
B = [2,4,6]
-> [1,2,3,4,5,6] mid = (3+4)/2 = 3.5 (中间偏左，中间偏右)
A = [1,3,5,7]
B = [2,4,6]
-> [1,2,3,4,5,6,7] mid = 4
2.2 find median in unsorted array。
5+5230
求解方案：quick select（♥♥♥） 。O(n) => find median(k=size/2) => find Kth
quick select 的题目：
- Kth Largest Element （5 in lintcode）在未排序的数组中，找从大到小的第k个数 Kth Smallest
- Numbers in Unsorted Array (461 in lintcode)
2.3 本题的求解思路
先求解 int findKth（int[ ] A, int[ ] B, int k） //不写实现，先写框架
主框架：double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
int n = A.size() + B.size();
if(n%2 == 0){
return ( findKth(A, B, n/2-1) + findKth(A, B, n/2) )/2;
}
return findkth(A, B, n/2);
}
时间复杂度：O( log(m+n) ) 这是挑战。决定了不能使用先merge sort，在找中位数
※ 根据时间复杂度推测算法：O（log(m+n)） => O( log((m+n)/2) ) => O（log（k）） T(k) = T(k/2) + O(1) => log(k) 如果能用O(1)的时间将找第k大变成第k/2大。
思路：
- step 1：比较A[k/2]和B[k/2]。
- step 2：将较小的数组中的k/2个数扔掉，用startIndex表示剩下的数
- step 3：截断后找第（k-k/2）大的数
- step 4：停止条件：a. A或B空，则为B或A 的第k大的数
b. k=1，则A、B第一个数的较小者。
特殊情况：
如果A数组不够，则直接扔掉B数组的前k/2个。用INT_MAX
2.4 代码
class Solution {
public:
/*
* @param A: An integer array
* @param B: An integer array
* @return: a double whose format is *.5 or *.0
*/
double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
// write your code here
int n = A.size() + B.size();
if(n%2 == 0){
return ( findKth(A,B,0,0,n/2) + findKth(A,B,0,0,n/2+1) )/2.0;
}
return findKth(A,B,0,0,n/2+1);
}
int findKth(vector<int> &A, vector<int> &B, int A_st, int B_st, int k){
if(A_st >= A.size()){
return B[B_st + k-1];
}
if(B_st >= B.size()){
return A[A_st + k-1];
}
if(k==1){
return min(A[A_st], B[B_st]);
}
int A_key = A_st + k/2 -1 < A.size()? A[A_st + k/2 -1] : INT_MAX;
int B_key = B_st + k/2 -1 < B.size()? B[B_st + k/2 -1] : INT_MAX;
if(A_key < B_key){
return findKth(A,B,A_st+k/2,B_st,k-k/2);
}
else{
return findKth(A,B,A_st,B_st+k/2,k-k/2);
}
}
};
第二部分：Subarray - 子数组（小视频）
基础知识：
1)前缀和
令PrefixSum[ i ] = A[0] + A[1] + … + A[i-1], PrefixSum[0] = 0。前缀和数组的大小为：n+1。
易知构造PrefixSum耗费O(n)的时间和 O(n)的空间。
如需计算子数组从下标i到下标j之间的所有数之和，则有 Sum[i~j] = PrefixSum[j+1] - PrefixSum[i]
PrefixSum[ i ]表示前i个数之和，即下标为0，1，2，…，i-1的数之和。
2)常见问题
哪个子数组最大？最小？ 子数组之和怎么样？之差？
3. Maximum Subarray（41 in lintcode）
3.0题目
http://www.lintcode.com/zh-cn/problem/maximum-subarray/
http://www.jiuzhang.com/solution/maximum-subarray/
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
3.1思路
以下标 j 结尾的数组有 j 个，根据Sum[i~j] = PrefixSum[j+1] - PrefixSum[i]，第一项不变，第二项改变，所以要想结果大，则第二项足够小.
以下标4的数结尾的最大子数组和为：PrefixSum[4] - min{ PrefixSum[0], PrefixSum[1], PrefixSum[2], PrefixSum[3] }
得到下标4的数结尾的最大子数组和，即需知道以0，1，2，3，4结尾的最小子数组和，于是可以计算以下标5结尾的子数组和，时间为O(1)。
从前往后记录最小子数组和。
3.2 代码
class Solution {
public:
/*
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> &nums) {
if(nums.size()==0){
return 0;
}
int preSum = 0, maxsa = INT_MIN, minSum = 0;
for(int i=0;i<nums.size();++i){
preSum += nums[i];
maxsa = max(maxsa, preSum-minSum);
minSum = min(minSum, preSum);
}
return maxsa;
}
};
3.3 follow up- minimum SubArray
直接将所有数取相反数，求Maximum- SubArray
3.3 follow up- minimum SubArray
直接将所有数取相反数，求Maximum- SubArray
4. Subarray Sum （138 in lintcode）
4.1 题目
http://www.lintcode.com/zh-cn/problem/subarray-sum/
http://www.jiuzhang.com/solution/subarray-sum/
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
4.2 思路
Sum[i~j] = PrefixSum[j+1] - PrefixSum[i] = 0 ==》 PrefixSum[j+1] = PrefixSum[i]
4.3 代码
class Solution {
public:
/*
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> subarraySum(vector<int> &nums) {
// write your code here
unordered_map<int,int> m;
vector<int> res;
int sum = 0;
m[sum] = -1;
for(int i=0;i<nums.size();++i){
sum += nums[i];
if(m.find(sum) != m.end()){
res.push_back(m[sum] + 1);
res.push_back(i);
return res;
}
m[sum] = i;
}
return res;
}
};
5.Subarray Sum Closest （139 in lintcode）
5.1 题目
http://www.lintcode.com/zh-cn/problem/subarray-sum-closest/
http://www.jiuzhang.com/solution/subarray-sum-closest/
给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最有一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置
给出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者 [0, 4]。
5.2 思路
PrefixSum[j+1] 和 PrefixSum[i] 尽量接近。
暴力求解：O(N^2)
将所有PrefixSum 排序，找尽量接近的两个数。
5.3 代码
class Solution {
public:
/*
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
struct node{
int val,pos;
node(int _val, int _pos):val(_val),pos(_pos){}
bool operator<(const node &o) const{
return (val < o.val)||(val == o.val && pos<o.pos);
}
};
vector<int> subarraySumClosest(vector<int> &nums) {
//write your code here
vector<node> s;
vector<int> results(2);
s.push_back(node(0,-1));
int sum = 0, len = nums.size();
for (int i = 0; i < len ; ++i) {
sum += nums[i];
s.push_back(node(sum, i));
}
sort(s.begin(), s.end());
len = s.size();
int ans = INT_MAX;
for (int i = 0; i < len-1; ++i)
if (abs(s[i+1].val - s[i].val) < ans) {
ans = abs(s[i+1].val - s[i].val);
results[0] = min(s[i].pos, s[i+1].pos)+1;
results[1] = max(s[i].pos, s[i+1].pos);
}
return results;
}
};