【LeetCode每日一题】—

【LeetCode每日一题】——912.排序数组

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【解题思路】
八【时间频度】
九【代码实现】
十【提交结果】

一【题目类别】

优先队列

二【题目难度】

中等

三【题目编号】

912.排序数组

四【题目描述】

给你一个整数数组 nums，请你将该数组升序排列。

五【题目示例】

示例 1：
- 输入：nums = [5,2,3,1]
- 输出：[1,2,3,5]
示例 2：
- 输入：nums = [5,1,1,2,0,0]
- 输出：[0,0,1,1,2,5]

六【题目提示】

$1 <= nums.length <= 5 * 10^4$
$5 * 10^4 <= nums[i] <= 5 * 10^4$

七【解题思路】

这道题没什么需要解释的，基础知识
即使用堆排序完成对目标数组的排序
具体细节可以参考下面的代码

八【时间频度】

时间复杂度： $O (n l o g n)$ ， $n$ 为传入的参数大小
空间复杂度： $O (n)$ ， $n$ 为传入的参数大小

九【代码实现】

Java语言版

class Solution {public int[] sortArray(int[] nums) {// 初始化小顶堆int[] heap = new int[nums.length + 1];int[] heapSize = {0};// 使用小顶堆排序数组for (int i = 0; i < nums.length; i++) {push(heap, heapSize, nums[i]);}int[] res = new int[nums.length];for (int i = 0; i < nums.length; i++) {res[i] = top(heap);pop(heap, heapSize);}// 返回结果return res;}// 交换数据public void swap(int[] heap, int a, int b) {int temp = heap[a];heap[a] = heap[b];heap[b] = temp;}// 向小顶堆中插入元素public void push(int[] heap, int[] heapSize, int x) {heap[++heapSize[0]] = x;for (int i = heapSize[0]; i > 1 && heap[i] < heap[i >> 1]; i >>= 1) {swap(heap, i, i >> 1);}}// 弹出小顶堆的堆顶元素public void pop(int[] heap, int[] heapSize) {heap[1] = heap[heapSize[0]--];int temp = heap[1];int i = 1;int j = 2;while (j <= heapSize[0]) {if (j != heapSize[0] && heap[j + 1] < heap[j]) {j++;}if (heap[j] < temp) {heap[i] = heap[j];i = j;j = i << 1;}else{break;}}heap[i] = temp;}// 返回小顶堆的堆顶元素值public int top(int[] heap) {return heap[1];}}

Python语言版

class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 初始化小顶堆heap = [0]heap_size = [0]# 使用小顶堆排序数组for num in nums:self.push(heap, heap_size, num)res = []for _ in range(len(nums)):res.append(self.top(heap))self.pop(heap, heap_size)# 返回结果return resdef swap(self, heap, a, b):"""交换数据"""heap[a], heap[b] = heap[b], heap[a]def push(self, heap, heap_size, x):"""向小顶堆中插入元素"""heap.append(x)heap_size[0] += 1i = heap_size[0]while i > 1 and heap[i] < heap[i >> 1]:self.swap(heap, i, i >> 1)i >>= 1def pop(self, heap, heap_size):"""弹出小顶堆的堆顶元素"""heap[1] = heap[heap_size[0]]heap_size[0] -= 1temp = heap[1]i = 1j = 2while j <= heap_size[0]:if j != heap_size[0] and heap[j + 1] < heap[j]:j += 1if heap[j] < temp:heap[i] = heap[j]i = jj = i << 1else:breakheap[i] = tempdef top(self, heap):"""返回小顶堆的堆顶元素值"""return heap[1]

C语言版

/*** Note: The returned array must be malloced, assume caller calls free().*/// 交换数据
void swap(int *a, int *b)
{int temp = *a;*a = *b;*b = temp;
}// 向小顶堆中插入元素
void push(int *heap, int *heapSize, int x)
{heap[++(*heapSize)] = x;for (int i = (*heapSize); i > 1 && heap[i] < heap[i >> 1]; i >>= 1){swap(&heap[i], &heap[i >> 1]);}
}// 弹出小顶堆的堆顶元素
void pop(int *heap, int *heapSize)
{heap[1] = heap[(*heapSize)--];int temp = heap[1];int i = 1;int j = 2;while (j <= (*heapSize)){if (j != (*heapSize) && heap[j + 1] < heap[j]){j++;}if (heap[j] < temp){heap[i] = heap[j];i = j;j = i << 1;}else{break;}}heap[i] = temp;
}// 返回小顶堆的堆顶元素值
int top(int *heap)
{return heap[1];
}int* sortArray(int* nums, int numsSize, int* returnSize)
{// 初始化小顶堆int* heap = (int*)malloc(sizeof(int) * (numsSize + 1));int heapSize = 0;// 使用小顶堆排序数组for (int i = 0; i < numsSize; i++){push(heap, &heapSize, nums[i]);}int* res = (int*)malloc(sizeof(int) * numsSize);for (int i = 0; i < numsSize; i++){res[i] = top(heap);pop(heap, &heapSize);}// 返回结果*returnSize = numsSize;free(heap);return res;
}