响应式网站建设如何,wordpress前端用户中心投稿,软件开发的生命周期,软文发稿平台有哪些前k个高频元素 题目描述解题思路代码实现 题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 解题思路
#xff08;1#xff09;先对给定的列表进行… 前k个高频元素 题目描述解题思路代码实现 题目描述
给你一个整数数组 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 i1 mid:my_stack.append(i)my_stack.append(mid-1)if mid j-1:my_stack.append(mid1)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], reverseTrue)x_res []u 0while uk:x_res.append(sorted_res[u][0])u1return x_res
