1、Java 代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 打印排序前的数组
System.out.println(Arrays.toString(nums));
// 执行快速排序操作
quickSort(nums,0,nums.length - 1);
// 打印排序后的数组
System.out.println(Arrays.toString(nums));
return null;
}
// 函数传入待排序数组 nums
// 排序区间的左端点 left
// 排序区间的右端点 right
private void quickSort(int[] nums,int left, int right){
// 如果 left 大于等于 right,说明该区间只有 1 个或者没有元素
if( left >=right ){
// 无需再递归划分后再排序,直接返回
return;
}
// 调用函数 partition,将 left 和 right 之间的元素划分为左右两部分
int mid = partition(nums,left,right);
// 划分之后,再对 mid 左侧的元素进行快速排序
quickSort(nums,left,mid - 1);
// 划分之后,再对 mid 右侧的元素进行快速排序
quickSort(nums,mid + 1,right);
}
private int partition(int[] nums, int left ,int right){
// 经典快速排序的写法
// 设置当前区间的第一个元素为基准元素
int pivot = nums[left];
// left 向右移动,right 向左移动,直到 left 和 right 指向同一元素为止
while( left < right ){
// 只有当遇到小于 pivot 的元素时,right 才停止移动
// 此时,right 指向了一个小于 pivot 的元素,这个元素不在它该在的位置上
while( left < right && nums[right] >= pivot ){
// 如果 right 指向的元素是大于 pivot 的,那么
// right 不断的向左移动
right--;
}
// 将此时的 nums[left] 赋值为 nums[right]
// 执行完这个操作,比 pivot 小的这个元素被移动到了左侧
nums[left] = nums[right];
// 只有当遇到大于 pivot left 才停止移动
// 此时,left 指向了一个大于 pivot 的元素,这个元素不在它该在的位置上
while( left < right && nums[left] <= pivot){
// 如果 left 指向的元素是小于 pivot 的,那么
// left 不断的向右移动
left++;
}
// 将此时的 nums[right] 赋值为 nums[left]
// 执行完这个操作,比 pivot 大的这个元素被移动到了右侧
nums[right] = nums[left];
}
// 此时,left 和 right 相遇,那么需要将此时的元素设置为 pivot
// 这个时候,pivot 的左侧元素都小于它,右侧元素都大于它
nums[left] = pivot;
// 返回 left
return left;
}
}
2、C++ 代码
3、Python 代码
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
for x in range(len(nums)):
print(nums[x])
self.quickSort(nums, 0 , len(nums) - 1)
print("------")
for x in range(len(nums)):
print(nums[x])
return None
def quickSort(self, nums: List[int], left : int , right : int ) :
if left >= right :
return
mid = self.partition(nums,left,right)
self.quickSort( nums , left , mid - 1 )
self.quickSort( nums , mid + 1 , right )
def partition(self, nums: List[int], left : int , right : int ) -> int :
pivot = nums[left]
while left < right :
while left < right and nums[right] >= pivot :
right -= 1
nums[left] = nums[right]
while left < right and nums[left] <= pivot :
left += 1
nums[right] = nums[left]
nums[left] = pivot
return left