110 lines
3.2 KiB
Python
110 lines
3.2 KiB
Python
##################### Section ##############################
|
||
# Section topic: Arrays and hashing
|
||
# Task name: Top K Frequent Elements
|
||
# Task:
|
||
# Given an integer array nums and an integer k, return the k most frequent
|
||
# elements within the array.
|
||
#
|
||
# The test cases are generated such that the answer is always unique.
|
||
#
|
||
# You may return the output in any order.
|
||
#
|
||
# Example 1:
|
||
#
|
||
# Input: nums = [1,2,2,3,3,3], k = 2
|
||
#
|
||
# Output: [2,3]
|
||
# Example 2:
|
||
#
|
||
# Input: nums = [7,7], k = 1
|
||
#
|
||
# Output: [7]
|
||
# Constraints:
|
||
#
|
||
# 1 <= nums.length <= 10^4.
|
||
# -1000 <= nums[i] <= 1000
|
||
# 1 <= k <= number of distinct elements in nums.
|
||
############################################################
|
||
|
||
##################### Section ##############################
|
||
# Section topic: Мой ход мыслей
|
||
# Заход 1
|
||
# Допустим возьмем простой массив, где в качестве индекса будет кол-во раз, которое
|
||
# встречается число в массиве nums
|
||
#
|
||
# Пример для первого кейса:
|
||
# cout = [0,1,2,3,4,5,6,7,8,9,...]
|
||
# 0,1,2,3,0,0,0,0,0,0,...
|
||
#
|
||
# Пример для второго кейса:
|
||
# cout = [0,1,2,3,4,5,6,7,8,9,...]
|
||
# 0,0,0,0,0,0,0,2,0,0,...
|
||
#
|
||
# Пример для неотсортированного массива
|
||
# nums = [4,1,2,5,5,2,3,1,6,3,2,0]
|
||
#
|
||
# cout = [0,1,2,3,4,5,6,7,8,9,...]
|
||
# 1,2,3,2,1,2,1,0,0,0,...
|
||
#
|
||
# => Заход не рабочий
|
||
#
|
||
# Заход 2
|
||
# Допустим будем хранить кол-во повторений в словаре, тогда на после первого
|
||
# просчета будем иметь:
|
||
#
|
||
# Первый случай:
|
||
# {1: 1, 2: 2, 3: 3}
|
||
#
|
||
# Второй случай:
|
||
# {7: 2}
|
||
#
|
||
# Получив такие словари берем, создаем массив с длиной len(nums) и заполненный нулями
|
||
# len(nums) = 6 => res = [[0],[0],[0],[0],[0],[0],[0]]
|
||
#
|
||
# {1: 1} => res[1].append(1)
|
||
# {2: 2} => res[2].append(2)
|
||
# {3: 3} => res[3].append(3)
|
||
#
|
||
#
|
||
# res = [[0],[1],[2],[3],[0],[0],[0]]
|
||
#
|
||
# Для семерок не интересно, попробуем для третьего примера первого кейса:
|
||
# nums = [4,1,2,5,5,2,3,1,6,3,2,0]
|
||
#
|
||
#
|
||
# Начинаем итерацию по полученному словарю
|
||
# {4: 1, 1: 2, 2: 3, 5: 2, 3: 2, 6: 1, 0: 1}
|
||
# res = [[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]]
|
||
#
|
||
# {4:1} => res[1].append(4)
|
||
# {1:2} => res[2].append(1)
|
||
# {2:3} => res[3].append(2)
|
||
# {5:2} => res[2].append(5)
|
||
# {3:2} => res[2].append(3)
|
||
# {6:1} => res[1].append(6)
|
||
# {0:1} => res[1].append(0)
|
||
############################################################
|
||
|
||
|
||
from typing import List
|
||
from collections import defaultdict
|
||
|
||
|
||
class Solution:
|
||
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
|
||
ic = defaultdict(int)
|
||
for n in nums:
|
||
ic[n] += 1
|
||
res = [[] for _ in range(0, len(nums)+1)]
|
||
for num,count in ic.items():
|
||
res[count].append(num)
|
||
return [item for sublist in res for item in sublist][-k:]
|
||
|
||
|
||
if __name__ == "__main__":
|
||
s = Solution()
|
||
nums = [7,7]
|
||
# nums = [1,2,2,3,3,3]
|
||
# nums = [4,1,2,5,5,2,3,1,6,3,2,0]
|
||
k = 1
|
||
print(s.topKFrequent(nums, k))
|