LeetCode
部分leetcode 题解
1. Merge k Sorted Lists
合并k个有序的链表为一个有序链表。
思路: 每次取k个链表头中最小的加入新的链表，直达k个链表都为空结束。 不过如果每次循环查找k个链表头最小的需要O(k)时间复杂度，整个 程序的时间复杂度为O(kn)，将会TLE。
优化方法: 维护一个含k个值的优先队列，每次取出最小值添加的链表
中，然后把最小值所在的链表的头的值放入优先队列中，直到优先队列
为空。 完整代码,
核心代码:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
res = ListNode(-1)
tmp = res
priority_queue = []
for i, node in enumerate(lists):
if node is None:
continue
heappush(priority_queue, (node.val, i))
lists[i] = node.next
while True:
try:
val, i = heappop(priority_queue)
except IndexError:
break
tmp.next = ListNode(val)
tmp = tmp.next
node = lists[i]
if node is not None:
heappush(priority_queue, (node.val, i))
lists[i] = node.next
return res.next
2. Find the duplicate number
思路: 根据鸽笼原理, 二分枚举[1, n], 假设mid, 如果小于等于mid的值大于mid个,
那么重复的数在[1, mid]之间, 否则在[mid+1, n]之间.完整代码
核心代码:
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low = 1
high = len(nums) - 1
while low <= high:
mid = low + (high - low) / 2
lte_sum = sum(x <= mid for x in nums)
if lte_sum > mid:
high = mid - 1
else:
low = mid + 1
return low
