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 = 03: n = len(nums)4: right = n-15: index = quick_sort(nums, left, right)6: while index != n-k do # determine if it is the Kth largest element7: 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 element1: pivot = nums[left]2: while left < right do3: while left < right & nums[right] >= pivot do4: right = right - 15: nums[left] = nums[right]6: while left < right & nums[left] <= pivot do7: left = left + 18: nums[right] = nums[left]9: nums[left] = pivot10: 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 failure2: # find the left boundary of target3: left = 04: right = len(nums)-15: while left < right do6: mid = (left+right)/27: if nums[mid] >= target then right = mid8: else left = mid+19: if nums[right] != target then return [-1,-1] # find the failure10: L = right11: # Find the right boundary of target12: left = 013: right = len(nums)-114: while left < right do15: mid = (left+right+1)/2 # prevent dead loops, mid needs add 116: if nums[mid] <= target return [-1,-1] left = mid17: else right = mid-118: 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 queue1: head = ListNode(0) # first node2: p = head3: q = PriorityQueue()4: for l in lists do5: if l is not None then q.put((l.val,l)) # all heads join the queue6: while q is not empty do7: val, node = q.get() # get the smallest value and node8: p.next = ListNode(val)9: p = p.next10: node = node.next11: if node is not None then q.put((node.val,node)) # enter header of list12: return head.nextk个链表有k个头结点，优先队列中蕴含k个结点，优先队列插入删除的工夫复杂度为\( O(logk) \)，总共有nk个结点须要被插入删除，所以工夫复杂度为\( O(knlogk) \)。