LeetCode 难题选做

4 Median of Two Sorted Arrays

求两个有序数组的中位数

解法1

二分答案,然后再在两个数组里面二分出有多少数比之小

复杂度 $O(log^2k)$

解法2

取两个数组的前k个元素,此时就转化为求两个数组的中位数

令 $i = \lfloor n / 2 \rfloor,j = \lceil n / 2 \rceil$
若$a_i < b_j$,那么:

  • $a_1$ 到 $a_i$ 均比 $b_j$ 到 $b_n$ 小,说明$a$中有 $n-i$ 个元素,$b$中有$n-j+1$个元素,共$n+1$个元素 比 $a_1$ 到 $a_i$ 大
  • 另一方面,说明$a$中有$i$个元素,$b$中有$j$个元素,共$n$个元素比$b_{j+1}$ 到 $b_n$小
    因此去掉$a$前$i$个元素和$b$后$i$个元素而中位数不变,对于$a_i \geq b_j$的情况可以类比,就这样一直递归下去。

复杂度 $O(logk)$

解法3(三个数组)

假设数组有无限长,即在原数组后补无限个无穷大
我们取 $l = \lfloor k / 3 \rfloor$,假设$a_l$是$a_l$,$b_l$,$c_l$中最小的
三个数组中,最多有$3l - 3$个比$a_l$小,所以$a_l$的排名是$3l - 2 < k$
然后我们去掉$a$的前$l$个元素,$k = k - l$,递归下去,每次$k$减少$1/3$

复杂度 $O(log_{3/2} k)$

细节及拓展

  • 重复元素?
  • 递归边界?

23 Merge k Sorted Lists

归并k个有序链表

  • 类似二路归并,每次从k个当中选一个最小的,时间 O(nk) (n为序列总长度
  • 用一个堆维护最小值,先把每个链表的第一个元素插入堆中,每次取堆顶元素,然后插入堆顶元素对应链表的第一个元素,时间 O(nlog(k))

41 First Missing Positive

找到数组中第一个缺少的正整数
要求 时间 O(n) 空间 O(1)

把 nums[i](1..n) 放在 nums[nums[i-1]-1]
顺序遍历,第一个 nums[i] != i+1 的数就是所求

1
2
3
4
5
6
7
8
9
int firstMissingPositive(vector<int>& nums) {
for(int i=0;i<nums.size();++i){
while(nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i]-1] != nums[i]){
swap(nums[i],nums[nums[i]-1]);
}
}
for(int i=0;i<nums.size();++i) if(i+1 != nums[i]) return i+1;
return nums.size()+1;
}

142 Linked List Cycle II

判断链表中是否有环,如果有,就返回环的起始位置。

设置两个指针,一个步长为1,另一个为2,若它们相交则说明有环。
假设他们走了k步相交,则说明环的长度为 2k - k = k
假设有链表有n个节点,那么从起点到环的起点要走n-k步,从起点到相交点走了k步,那么从相交点到起点也要走n-k步。
因此设置两个指针,分别从起点和相交点出发,步长为1,相交后即为环的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode *detectCycle(ListNode *head) {
ListNode *l, *r;
l = r = head;
while(l && r){
l = l->next;
r = r->next;
if(r == nullptr) return nullptr;
r = r->next;
if(l == r){
l = head;
while(l != r) l = l->next,r = r->next;
return l;
}
}
return nullptr;
}

264 Ugly Number II

丑数即只含质因子2 3 5的数,一般认为1是第一个丑数
求第n个丑数

三个指针分别指向下一步需要*2/3/5的数的位置,每次选最小的数添加到序列后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int nthUglyNumber(int n) {
vector<int> ug(n);
ug[0] = 1;
int i2,i3,i5;
i2 = i3 = i5 = 0;
for(int i=1;i<n;++i) {
long long cur = min(ug[i2]*2LL,min(ug[i3]*3LL,ug[i5]*5LL));
ug[i] = cur;
if(cur == ug[i2]*2) ++i2;
if(cur == ug[i3]*3) ++i3;
if(cur == ug[i5]*5) ++i5;
}
return ug[n-1];
}

324 Wiggle Sort II

摆动排序
一个无序数组,排序使其满足nums[0] < nums[1] > nums[2] < nums[3]....

  • 排序后找到中位数mid,然后从前向后奇数位上放>mid的数,从后往前偶数位上放<mid的数,其余位置放mid,时间 O(nlog(n)) 空间 O(n)
  • 通过nth_element函数找到中位数(quickselect,保证了比中位数小的数在左边,大的在右边),我们将设数组下标映射为1 3 5... 0 2 4...(通过函数(2*p+1)%(n|1)实现),然后等价于将<mid的数放在左边,将>mid的数放在右边,这就是一个partition的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void wiggleSort(vector<int>& nums) {
int n = nums.size();
nth_element(nums.begin(), nums.begin()+nums.size()/2, nums.end());
int mid = nums[n/2];

auto T = [=](int p){ return (2*p+1)%(n|1); };

int i = 0, j = 0, k = n-1;
while(i <= k){
if(nums[T(i)] > mid)
swap(nums[T(i++)],nums[T(j++)]);
else if(nums[T(i)] < mid)
swap(nums[T(i)],nums[T(k--)]);
else
++i;
}
}
  • <= => 版本 280 Wiggle Sort (直接扫一遍并交换就可以了)