【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\ast 10^4$
• $-5\ast 10^4<=nums[i]<=5\ast 10^4$

七【解题思路】

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

八【时间频度】

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

九【代码实现】

1. 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];
    }

}

2. 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 res

    def 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] += 1
        i = heap_size[0]
        while i > 1 and heap[i] < heap[i >> 1]:
            self.swap(heap, i, i >> 1)
            i >>= 1
    
    def pop(self, heap, heap_size):
        """弹出小顶堆的堆顶元素"""
        heap[1] = heap[heap_size[0]]
        heap_size[0] -= 1
        temp = heap[1]
        i = 1
        j = 2
        while j <= heap_size[0]:
            if j != heap_size[0] and heap[j + 1] < heap[j]:
                j += 1
            if heap[j] < temp:
                heap[i] = heap[j]
                i = j
                j = i << 1
            else:
                break
        heap[i] = temp
    
    def top(self, heap):
        """返回小顶堆的堆顶元素值"""
        return heap[1]

3. 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;
}

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版