数组中的第K大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

  1. class Solution(object):
  2.     def findKthLargest(self, nums, k):
  3.         # 方法一：这里使用了自建堆，可以使用[0]等索引方法
  4.         heap = [x for x in nums[:k]]
  5.         heapq.heapify(heap)
  6.         for i in range(k, len(nums)):
  7.             if nums[i] > heap[0]:
  8.                 heapq.heappop(heap)
  9.                 heapq.heappush(heap, nums[i])
  10.         return heap[0]
  12. class Solution(object):
  13.     def findKthLargest(self, nums, k):
  14.         # 方法二：堆的另一种方法，常用
  15.         heap = []
  16.         for i in nums:
  17.             heapq.heappush(heap, i)
  18.             if len(heap) > k:
  19.                 heapq.heappop(heap)
  20.         return heap[0]
  22. class Solution(object):
  23.     def findKthLargest(self, nums, k):
  24.         # 方法三：快排，但不是最优解
  25.         # 第k个最大的元素，即升序排列后，index为len(nums)-k
  26.         k = len(nums) - k
  27.         low = 0
  28.         high = len(nums) - 1
  29.         while low <= high:
  30.             p = self.sort_nums(nums, low, high)
  31.             if k < p:
  32.                 high = p-1
  33.             elif k > p:
  34.                 low = p+1
  35.             else:
  36.                 return nums[p]
  37.         return -1
  39.     def sort_nums(self, alist, low, high):
  40.         mid_value = alist[low]
  41.         while low <high:
  42.             while low < high and alist[high] >= mid_value:
  43.                 high -= 1
  44.             alist[low] = alist[high]
  46.             while low < high and alist[low] <= mid_value:
  47.                 low += 1
  48.             alist[high] = alist[low]
  49.         alist[low] = mid_value
  50.         return low
  52. # Go语言版
  53. func findKthLargest(nums []int, k int) int {
  54.     return sort_nums(nums,k)
  55. }
  57. func sort_nums(nums []int, k int) int {    //快排
  58.     i := 0
  59.     j := len(nums) - 1
  60.     pivot := nums[0]
  61.     for i < j{
  62.         for i < j && nums[j] < pivot{
  63.             j--
  64.         }
  65.         if i < j{
  66.             nums[i], nums[j] = nums[j], nums[i]
  67.             i++
  68.         }
  69.         for i < j && nums[i] > pivot{
  70.             i++
  71.         }
  72.         if i < j{
  73.             nums[i], nums[j] = nums[j], nums[i]
  74.             j--
  75.         }
  76.     }
  78.     if i+1 == k{                     
  79.         return pivot  //   位子恰好就是K-1返回结果
  80.     }else if i+1 < k{
  81.         return sort_nums(nums[i+1:], k-i-1)       //以pivot为断点，在后半部分数组中进行查找
  82.     }else{
  83.         return sort_nums(nums[:i], k)    //在前半部分数组中进行查找
  84.     }
  85. }

前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
输入: nums = [1], k = 1
输出: [1]

  1. class Solution(object):
  2.     def topKFrequent(self, nums, k):
  3.         dicts = {}
  4.         res = []
  5.         for i in range(len(nums)):
  6.             if nums[i] in dicts:
  7.                 dicts[nums[i]] += 1
  8.             else:
  9.                 dicts[nums[i]] = 1
  11.         for key, value in dicts.items():
  12.             heapq.heappush(res, (value, key))
  13.             if len(res) > k:
  14.                 heapq.heappop(res)
  15.         return [x[-1] for x in res]

前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。
输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

  1. class Solution(object):
  2.     def topKFrequent(self, words, k):
  3.         dicts = {}
  4.         res = []
  5.         for i in range(len(words)):
  6.             if words[i] not in dicts:
  7.                 dicts[words[i]] = 1
  8.             else:
  9.                 dicts[words[i]] += 1
  10.         for key, value in dicts.items():
  11.             heapq.heappush(res, (-value, key))
  13.         tmp = []
  14.         for _ in range(k):
  15.             tmp.append(heapq.heappop(res)[-1])
  16.         return tmp

根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
输入:
“tree”
输出:
“eert”
解释:
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
输入:
“cccaaa”
输出:
“cccaaa”
解释:
‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。
注意”cacaca”是不正确的，因为相同的字母必须放在一起。

  1. class Solution(object):
  2.     def frequencySort(self, s):
  3.         dicts = {}
  4.         lists = []
  5.         res = ''
  7.         # 计数
  8.         for i in range(len(s)):
  9.             if s[i] in dicts:
  10.                 dicts[s[i]] += 1
  11.             else:
  12.                 dicts[s[i]] = 1
  14.         # 根据次数使用堆排序
  15.         for key, value in dicts.items():
  16.             heapq.heappush(lists, (value, key))
  18.         # 拼凑字符串
  19.         while lists:
  20.             tmp = heapq.heappop(lists)
  21.             res = tmp[0]*tmp[-1] + res
  22.         return res