TopK

Top K Largest element

• 解法一：直接排序，输出倒数第k个数；时间复杂度为O(nlogn)

• 解法二：
  思路：selection sort的变种，我们不关心topK个元素的排序，我们只关心topK元素中最小的那个。 （1）找到nums[0:k]（前k个元素）中最小的元素kmin（时间复杂度k） （2）加入nums[k], nums[k+1]……

  • 若 nums[i] > kmin，则用nums[i]代替kmin，重新寻找k个数中的最小元素
  • 若 nums[i] <= kmin，则continue 最坏情况下每次都需要更新kmin，时间复杂度为O(n*k)

    class Solution(object):
          def findMin(self, nums, k):
                min_i = 0
                for i in range(k):
                  if ( nums[i] < nums[min_i] ):
                        min_i = i
                return min_i
          def findKthLargest(self, nums, k):
                sol = Solution()
                min_i = sol.findMin(nums, k)
                for i in range(k, len(nums)):
                  if ( nums[i] <= nums[min_i] ): continue
                  else:
                        nums[min_i] = nums[i]
                        min_i = sol.findMin(nums, k)
                return nums[min_i]

• 解法三：
  思路：quick sort的变种，假设一次排序后pivot元素处于nums[mid]:
  • 若 mid == n-k，则返回nums[mid]
  • 若 mid < n-k，则对右侧数组继续排序，求topK；
  • 若 mid > n-k，咋对左侧数组继续排序，求top(mid-n+k)

    class Solution(object):
          def findKthLargest(self, nums, k):
            sol = Solution()
            pivot = nums[-1]
            i, j = 0, len(nums)-2
            while ( i <= j ):
             if ( nums[i] < pivot ): i += 1
             else:
                    nums[i], nums[j] = nums[j], nums[i]
                    j -= 1
            mid = j+1
            nums[mid], nums[-1] = nums[-1], nums[mid]
            if ( mid == len(nums)-k ): return nums[mid]
            if ( mid < len(nums)-k ): 
            return sol.findKthLargest(nums[mid+1:], k)
            if ( mid > len(nums)-k ): 
            return sol.findKthLargest(nums[0:mid],mid - len(nums) + k)

• 解法四：
  这个解法可以用来动态维护topK元素。
  思路：heap sort的变种，类似解法二，利用最小堆来维护最大的k个元素，时间复杂度O(logK)。
  • step1: 对前k个数建立最小堆
  • step2: 遍历余下的数，若nums[i]大于topK中的最小值，则用nums[i]替代最小堆的根值，同时修复最小堆
  • step3: 返回最小堆根值。

class Solution(object):
  def helper(self, nums, iend, i):
    sol = Solution()
    imin, nmin = i, nums[i]
    if ( 2*i+1 <= iend and nums[2*i+1] < nmin ):
      imin, nmin= 2*i+1, nums[2*i+1]
    if ( 2*i+2 <= iend and nums[2*i+2] < nmin ):
      imin, nmin = 2*i+2, nums[2*i+2]
    if ( imin != i ):
      nums[i], nums[imin] = nums[imin], nums[i]
    sol.helper(nums, iend, imin)

  def build_heap(self, nums, i):
    sol = Solution()
     for i in range(len(nums)-1, -1, -1):
       sol.helper(nums, len(nums)-1, i)

  def findKthLargest(self, nums, k):
    sol = Solution()
    tmp = nums[0:k]
    sol.build_heap(tmp, len(tmp)-1)
    for i in range(k+1, len(nums)):
      if ( nums[i] > tmp[0] ):
        tmp[0] = nums[i]
        sol.helper(tmp, len(tmp)-1, 0)
    return tmp[0]

Top K Frequent element