关于算法:Assignment1DivideandConquer

6次阅读

共计 3196 个字符，预计需要花费 8 分钟才能阅读完成。

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) $。

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) $。

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.next

k 个链表有 k 个头结点，优先队列中蕴含 k 个结点，优先队列插入删除的工夫复杂度为 $O(logk) $，总共有 nk 个结点须要被插入删除，所以工夫复杂度为 $O(knlogk) $。

正文完