采用非递归快排实现找出数组中的前k个高频元素（python）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

解题思路

（1）先对给定的列表进行快速排序，按升序排（这里采用的非递归方式，因为最近在学习非递归快速排序的思想）
（2）非递归快速排序思想：找一个基准进行一趟快排，一般会产生两个区间，可以用一个栈保存这两个区间（区间类型[start,end]），并归位一个元素。
这是一次快速排序的结果，如果采用非递归，则需要对每一个入栈的区间一次次缩小范围，即循环判断栈 若不为空，则出栈，也就是拿出一个区间，继续下一趟快排，再归位一个元素，然后再判断产生的区间入栈，直到栈为空。
（3）快速排序结束后，原数组有序，这里找前k个高频元素，用字典存储每个元素的出现次数，并对字典进行降序排序，输出前k个key值。

代码实现

def frequentlyHighNo(nums, k):my_stack = []if len(nums)<=1:return numsmy_stack.append(0)my_stack.append(len(nums)-1)flag = 0while len(my_stack):j = my_stack.pop()i = my_stack.pop()begin = iend = jprint(begin, end)temp = nums[begin]print(temp)while begin < end:while begin < end and temp <= nums[end]:end -= 1while begin < end and temp >= nums[begin]:begin += 1if begin < end:nums[begin], nums[end] = nums[end], nums[begin]nums[i], nums[begin] = nums[begin], nums[i]mid = beginif i+1 < mid:my_stack.append(i)my_stack.append(mid-1)if mid < j-1:my_stack.append(mid+1)my_stack.append(j)res = {}for num in nums:if num not in res.keys():res[num] = 1else:res[num] += 1print(res)sorted_res = sorted(res.items(), key= lambda item: item[1], reverse=True)x_res = []u = 0while u<k:x_res.append(sorted_res[u][0])u+=1return x_res