Assignment1_Divide_and_Conquer
1 Divide and Conquer
Given an integer array nums and an integer k, please return the k-th largest element in the
array. Your algorithm’s runtime complexity must be in the order of \(O(n) \), prove the correctness and analyze the complexity.(k is much smaller than n, n is the length of the array.)
利用疾速排序的办法，每一次快排都能够确定一个元素的地位，即 pivot 的索引，pivot 右边的都小于等于它，左边的都大于等于它。这样就能够将 pivot 的索引与（n-k）比拟，如果相等，那么该索引对应的值就是数组中第 k 大的数；如果索引小于（n-k），那么第 k 大的数在该索引的左边，下一轮快排便是对索引的右侧元素进行排序；如果索引大于（n-k），那么第 k 大的数在该索引的右边，下一轮快排便是对索引的左侧元素进行排序。
pseudo-code
function kth_largest_element(nums,k)
1: if len(nums)<1 | k < 0 | k > len(nums) then return
2: left = 0
3: n = len(nums)
4: right = n-1
5: index = quick_sort(nums, left, right)
6: while index != n-k do # determine if it is the Kth largest element
7: if index > n-k then right = index-1
8: if index < n-k then left = index+1
9: index = quick_sort(nums, left, right)
10: return nums[index]
function quick_sort(nums, left, right)
# quicksort determines the index of an element
1: pivot = nums[left]
2: while left < right do
3: while left < right & nums[right] >= pivot do
4: right = right - 1
5: nums[left] = nums[right]
6: while left < right & nums[left] <= pivot do
7: left = left + 1
8: nums[right] = nums[left]
9: nums[left] = pivot
10: return left个别，快排是对参考元素两边都进行递归，但在解决这个问题时只思考参考元素的一边，只对一边进行递归，依据索引与（n-k）的比拟抉择对其中一遍进行递归。第一次划分须要遍历约 n 个数，第二次须要遍历约 n / 2 个数，……，这样递归上来，后果趋近于 2n，所以该算法的工夫复杂度整体上为 \(O(N) \)。
4 Divide and Conquer
Given an array of integers nums sorted in ascending order, find the starting and ending
position of a given target value. If the target is not found in the array, return [-1, -1]. For
example, if the array is [5, 7, 7, 8, 8, 10] and the target is 8, then the output should be [3, 4].
Your algorithm’s runtime complexity must be in the order of $O(log n)$, prove the correctness
and analyze the complexity.
查找枯燥递增的整数数组的其中一个元素的开始地位和完结地位，能够利用二分法来实现。两次二分：第一次查找第一个 >=target 的地位，即元素最左边界；第二次查找最初一个 <=target 的地位，即最右边界。查找胜利则返回两个地位下标，否则返回 [-1,-1]。
pseudo-code
function searchIndex(nums, target)
1: if len(nums)<1 then return [-1,-1] # find the failure
2: # find the left boundary of target
3: left = 0
4: right = len(nums)-1
5: while left < right do
6: mid = (left+right)/2
7: if nums[mid] >= target then right = mid
8: else left = mid+1
9: if nums[right] != target then return [-1,-1] # find the failure
10: L = right
11: # Find the right boundary of target
12: left = 0
13: right = len(nums)-1
14: while left < right do
15: mid = (left+right+1)/2 # prevent dead loops, mid needs add 1
16: if nums[mid] <= target return [-1,-1] left = mid
17: else right = mid-1
18: R = right
19: return [L,R] 二分查找的工夫复杂度为 \(O(logn) \)，会进行两次二分查找，因而工夫复杂度为 \(O(logn) \)。
6 Divide and Conquer
Given an array of k linked-lists lists, each linked-list is sorted in ascending order. Given an
\(O(knlogk) \)algorithm to merge all the linked-lists into one sorted linked-list. (Note that the
length of a linked-lists is n)
将 k 个升序链表合并为一个升序链表。对于 mergeKLists 函数，将这 k 个升序链表的头结点输出到优先队列中，只有队列不为空，优先队列便会选取其中最小的结点，而后输入最小结点将其退出到新链表中，而这个最小结点的链表的头结点又输出到队列，保障队列中含每个链表的结点，始终循环直到队列为空，最终新链表按升序排列好这 k 个链表，可证实算法的正确性。
pseudo-code
function mergeKLists(lists)
# Compare all linked-lists' header and take the smallest -- Using priority queue
1: head = ListNode(0) # first node
2: p = head
3: q = PriorityQueue()
4: for l in lists do
5: if l is not None then q.put((l.val,l)) # all heads join the queue
6: while q is not empty do
7: val, node = q.get() # get the smallest value and node
8: p.next = ListNode(val)
9: p = p.next
10: node = node.next
11: if node is not None then q.put((node.val,node)) # enter header of list
12: return head.nextk 个链表有 k 个头结点，优先队列中蕴含 k 个结点，优先队列插入删除的工夫复杂度为 \(O(logk) \)，总共有 nk 个结点须要被插入删除，所以工夫复杂度为 \(O(knlogk) \)。