$O(n)$ 找出数组中特殊的数

  • LeetCode 搜 Single Number

数组中只有一个数出现1次,其他数都出现了2次

直接求异或和

数组中只有一个数出现1次,其他数都出现了3次

每一位加起来%3

one 存的是出现一次的位,如果这一位出现两次,那么只能为0 ((1+2)%3)
two 存的是出现两次的位,如果这一位出现一次,那么只能为0 ((2+1)%3)

1
2
3
4
5
6
7
8
9
int singleNumber(vector<int>& nums) {
int one = 0,two = 0;
for(int i=0;i<nums.size();++i)
{
one = (one^nums[i]) & ~two;
two = (two^nums[i]) & ~one;
}
return one;
}

数组中只有一个数出现2次,其他数都出现了3次

和上一题类似,不过返回two就可以了

数组中有两个出现1次的数字,其他数字都出现2次,找出这2个数字

先求异或和,然后找到为1的任意一位(两个数这一位肯定不同)
然后分别将数组中与这位为1的和这位不为1的数异或起来,就为这两个数

给定一个大小为 n+1 的数组,每个元素都是[1,n]内的整数,且只有一个数重复,找出这个重复的数

将 nums[0] 与 nums[nums[0]] 交换,直到 nums[nums[0]] = nums[0]
最后 nums[0] 即为答案

复杂度 时间 O(n) 空间 O(1)

1
2
3
4
int theOnlyRepeat(vector<int>& nums) {
while(nums[nums[0]] != nums[0]) swap(nums[0],nums[nums[0]]);
return nums[0];
}

股票问题

  • LeetCode 搜 Majority Element
  • 参考

一个序列,代表股票每天的价格,每天选择买入或卖出,求最大收益

只能买入卖出一次

维护一个最小值的股票值,扫一遍维护最大收益

时间 O(n) 空间 O(1)

能买入卖出多次

既每个单调上升区间的最大值减最小值的和,等价于所有p[i] - p[i-1]为正值的和

时间 O(n) 空间 O(1)

能买入卖出两次

先扫一遍维护,并记录d[i],为前i个的最优值
然后倒着扫一遍,更新最大值

时间 O(n) 空间 O(n)

维护两个最小值的股票,和买第一次和第二次的最小值

1
2
3
4
5
6
7
8
9
10
11
int mn1,mn2,mx1,mx2
mn1 = mn2 = -INF;
mx1 = mx2 = 0;
for(int i=0;i<n;++i)
{
mx2 = max(mx2,prices[i]+mn2);
mn2 = max(mn2,mx1-prices[i]);
mx1 = max(mx1,price[i]+mn1);
mn1 = max(mn1,-prices[i]);
}
return mx2;

时间 O(n) 空间 O(1)

能买入卖出k次

时间 O(nk) 空间 O(k)

即上面那个做法的扩展
维护k个最小值的股票,和卖第一次和第二次的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int INF = 0x3f3f3f3f;
int maxProfit(int k, vector<int>& prices) {
if(k == 0) return 0;
int n = prices.size();
if(k >= n/2){
int ans = 0;
for(int i=1;i<n;++i) ans += max(0,prices[i]-prices[i-1]);
return ans;
}
vector<int> mn(k,-INF),mx(k,0);
for(int i=0;i<n;++i){
for(int j=k-1;j>0;--j){
mx[j] = max(mx[j],mn[j]+prices[i]);
mn[j] = max(mn[j],mx[j-1] - prices[i]);
}
mx[0] = max(mx[0],mn[0]+prices[i]);
mn[0] = max(mn[0],- prices[i]);
}
return mx[k-1];
}

能买入卖出多次,有冻结期k (即卖k天出后才能买入)

d[i] = max(cur+a[i],d[i-1])
cur = max(cur,d[i-k]-a[i])

时间 O(n) 空间 O(n)

每天都可以买入,可以一次卖出多次的买入

即一直买入,到全局最高点卖出
对于全局最高点后的部分再递归处理

时间 O(nlogn) 空间 O(1)

转化为积水问题:

有一个非负整数数组,代表不同的高度的墙,现在在其中填满水,问水的体积

这个问题相当于在数组前加一个极大值
两个指针从两端向中间扫,分别走到峰值
然后从峰值较小的一端向另一端统计答案,直到峰值小于当前值

时间 O(n) 空间 O(1)

每次交易需要手续费

相当于降低了卖价(或提高了买价)
可以按之前的思路做

寻找数组中的多数元素

  • LeetCode 搜 Majority Element

排序可以做到时间 O(nlogn) 空间 O(1)
Boyer-Moore Majority Vote algorithm可以做到 时间 O(n) 空间 O(1)

出现大于 n/2 次的元素

对于数组中一对一对的元素,如果不同就淘汰,相同就保留
最后留下来的必定是大于 n/2 次的元素
可以写成下面这样

1
2
3
4
5
6
7
8
9
10
11
12
int majorityElement(vector<int>& nums) {
int num = nums[0],cnt = 0;
for(int i=0;i<nums.size();++i){
if(nums[i] == num)
++cnt;
else if(cnt == 0)
num = nums[i],cnt = 1;
else
--cnt;
}
return num;
}

出现大于 n/3 次的元素

从上面的解法扩展一下,答案有可能为 0,1,2 个
我们开两个 num 和 cnt 记录,最后再验证一下即可

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
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size(),cnt0,cnt1,num0,num1;
vector<int> ans;
if(!n) return ans;
cnt0 = cnt1 = 0;
num0 = num1 = nums[0];
for(int i=0;i<n;++i) {
if(num0 == nums[i])
++cnt0;
else if(num1 == nums[i])
++cnt1;
else if(cnt0 == 0)
num0 = nums[i],cnt0 = 1;
else if(cnt1 == 0)
num1 = nums[i],cnt1 = 1;
else {
--cnt0;
--cnt1;
}
}
cnt0 = cnt1 = 0;
for(int i=0;i<n;++i)
{
if(nums[i] == num0) ++cnt0;
else if(nums[i] == num1) ++cnt1;
}
if(cnt0 > n/3) ans.push_back(num0);
if(cnt1 > n/3) ans.push_back(num1);
return ans;
}

K-Sum

经典的 K-Sum 问题,在数组中找K个数,和恰为 target

2Sum

排序 + Two Pointer

排序后,两个指针从头尾向中间扫
如果 nums[l] + numss[r] < target++l
如果 nums[l] + numss[r] > target--r

复杂度 时间 O(nlogn) + O(n) = O(nlogn) 空间 O(1)

HashTable

扫一遍
统计 hash[target - num[i]] ,查 hash[num[i]]

复杂度 时间 O(n) 空间 O(n)

3Sum

转化为2Sum

先排序,枚举其中一个元素的位置i, target = target - nums[i]
j,k 用 2Sum 的头尾指针的方法,保证 i < j < k

复杂度 时间 O(nlogn) + O(n^2) = O(n^2) 空间 O(1)

KSum

转化为2Sum

先排序,枚举两个数,再做 2Sum
复杂度 时间 O(nlogn) + O(n^(k-1)) = O(n^(k-1)) 空间 O(1)

理论最优

k-SUM can be solved more quickly as follows.

For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether Scontains both some number x and its negation −x. The algorithm runs in O(n^(k/2)logn) time.

For odd k: Compute the sorted list S of all sums of (k−1)/2 input elements. For each input element a, check whether S contains both x and a−x, for some number x. (The second step is essentially the O(n^2)-time algorithm for 3SUM.) The algorithm runs in O(n^((k+1)/2)) time.

Both algorithms are optimal (except possibly for the log factor when k is even and bigger than 2) for any constant k in a certain weak but natural restriction of the linear decision tree model of computation.

Rotated Sorted Array

  • LeetCode 搜 Rotated

即排好序的数组做一次旋转

Find Minimum in Rotated Sorted Array

找到旋转数组中的最小值

根据 nums[m] 和 nums[r] 的关系逼近就可以了

1
2
3
4
5
6
7
8
9
int findMin(vector<int>& nums) {
int l = 0,r = int(nums.size())-1;
while(l < r){
int m = l + (r-l)/2;
if(nums[m] > nums[r]) l = m + 1;
else r = m;
}
return nums[l];
}

含重复元素

如果含重复元素,加一种 nums[m] == nums[r] 的情况
nums[m] == nums[r]时,r = r - 1,即缩小这个区间

1
2
3
4
5
6
7
8
9
10
11
12
13
int findMin(vector<int>& nums) {
int l = 0,r = int(nums.size()) - 1;
while(l < r) {
int m = l + (r-l)/2;
if(nums[m] > nums[r])
l = m + 1;
else if(nums[m] == nums[r])
r = r - 1;
else
r = m;
}
return nums[l];
}

Search in Rotated Sorted Array

我们需要根据a[l]和a[m]的关系确定target所在的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int search(vector<int>& nums, int target) {
vector<int>& a = nums;
int l = 0, r = int(nums.size()) - 1;
if(r == -1) return -1;
while(l < r) {
int m = l + (r-l)/2;
if(a[m] == target) return m;
if(a[l] <= a[m]) {
if(target >= a[l] && target <= a[m])
r = m;
else
l = m + 1;
}
else {
if(target > a[m] && target <= a[r])
l = m + 1;
else
r = m;
}
}
return a[l]==target?l:-1;
}

含重复元素

原理类似,加一种a[l] == a[m]的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool search(vector<int>& nums, int target) {
vector<int>& a = nums;
int l = 0, r = int(nums.size()) - 1;
if(r == -1) return false;
while(l < r) {
int m = l + (r-l)/2;
if(a[m] == target) return true;
if(a[l] < a[m]) {
if(target >= a[l] && target <= a[m])
r = m;
else
l = m + 1;
}
else if(a[l] > a[m]){
if(target > a[m] && target <= a[r])
l = m + 1;
else
r = m;
}
else ++l;
}
return a[l]==target?true:false;
}

位运算

完美洗牌问题

给定一个已经降序排好序的正数数组,要求按「最小、最大、次小、次大……」的顺序重新排序
要求时间复杂度O(n),空间复杂度O(1)