1. lc 23 - 合并K个升序链表
题目来源
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
1.1 解题思路
分治合并 - 将 k 个链表配对并将同一对中的链表合并； - 第一轮合并以后，k 个链表被合并成了 k/2 个链表 - 重复这一过程，链表合并为 k/4, k/8, 直到我们得到了最终的有序链表。
具体流程图：
1.2 时间复杂度
- 时间复杂度：考虑递归「向上回升」的过程——第一轮合并 k/2 组链表，每一组的时间代价是 O(2n)；第二轮合并 k/4 组链表，每一组的时间代价是 O(4n) ...... 递归的每一层是O(kn), 一共log(k)层。所以总的时间代价是 O (∑ k/2^i × 2^i*n) = O(kn×logk)，故渐进时间复杂度为 O(kn×logk)。
- 空间复杂度：一共log(k)层递归。递归会使用到 O(logk) 空间代价的栈空间。
1.3 代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists)==0 :
return None
res = lists
while len(res) > 1:
merge_time = len(res)//2
if len(res)%2 == 1: merge_time += 1
tmp = []
for i in range(merge_time):
if (i+1)*2 <= len(res):
tmp.append(self.merge(res[i*2],res[i*2+1]))
else:
tmp.append(res[-1])
res = tmp
return res[0]
def merge(self, l1: List[ListNode],l2: List[ListNode] ):
move = dummy_node = ListNode(10086)
while l1 or l2:
if not l1:
move.next = l2
l2 = l2.next
elif not l2:
move.next = l1
l1 = l1.next
elif l1.val <= l2.val and l1 and l2:
move.next = l1
l1 = l1.next
elif l1.val > l2.val and l1 and l2:
move.next = l2
l2 = l2.next
move = move.next
return dummy_node.next
|
2. lc 26 - 删除排序数组中的重复项
题目来源
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
2.1 解题思路
简单题。删除重复元素，返回改动后列表长度。
2.2 时间复杂度
2.3 代码
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
pointer = 0
tmp = float('inf')
while pointer < len(nums):
if nums[pointer] != tmp:
tmp = nums[pointer]
pointer += 1
else:
del nums[pointer]
return len(nums)
|
3. lc 33 - 搜索旋转排序数组
题目来源
3.1 解题思路
看到排序问题，就想到二分查找。二分查找 难就难在，arr[mid]跟谁比。我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。
由于数组由两部分组成，左边递增区域，和右边递增区域。可以感知到，分2种情况讨论。
第一种情况：mid的值在左边区域内，我们可以判断，1）当target在left值和mid值之间时，target在一个显示的递增区间。我们将在left值和mid值之间进行二分查找；2）否则，我们在mid值到right值之间进行二分查找。
第二种情况：mid的值在右边区域内，我们可以判断，1）当target在mid值和right值之间时，target在一个显示的递增区间。我们将在mid值和right值之间进行二分查找；2）否则，我们在left值到mid值之间进行二分查找。
3.2 时间复杂度
3.3 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right)//2
if target == nums[mid]:
return mid
if nums[mid] < nums[left]:
if nums[mid] <= target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
elif nums[mid] >= nums[left]:
if nums[left] <= target and target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
|
