What is the optimal time complexity for sorting an array?

The optimal time complexity for sorting an array is O(n log n), which is achievable by algorithms like Merge Sort, Quick Sort, and Heap Sort.

Can I use built-in sorting functions in this problem?

No, you must implement your own sorting algorithm to meet the constraints of the problem.

What is the difference between Merge Sort and Quick Sort?

Merge Sort guarantees O(n log n) time complexity but requires O(n) space, while Quick Sort has an average O(n log n) time complexity but can degrade to O(n^2) in the worst case.

How does Heap Sort compare to Merge Sort?

Heap Sort has O(n log n) time complexity and O(1) space complexity, making it more space-efficient than Merge Sort, which has O(n) space complexity.

What should I consider when choosing a sorting algorithm?

When choosing a sorting algorithm, consider the time complexity, space complexity, and whether the algorithm handles edge cases like duplicates or large input sizes efficiently.

#912

Medium

auto_awesome堆

LeetCode 题解工作台

排序数组

给你一个整数数组 nums ，请你将该数组升序排列。你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(nlog(n)) ，并且空间复杂度尽可能小。示例 1：输入： nums = [5,2,3,1] 输出： [1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2…

数组分治排序堆（优先队列）归并排序

题目描述

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。

提示：

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

lightbulb

解题思路

方法一：快速排序

快速排序是一种高效的排序算法。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(l, r):
            if l >= r:
                return
            x = nums[randint(l, r)]
            i, j, k = l - 1, r + 1, l
            while k < j:
                if nums[k] < x:
                    nums[i + 1], nums[k] = nums[k], nums[i + 1]
                    i, k = i + 1, k + 1
                elif nums[k] > x:
                    j -= 1
                    nums[j], nums[k] = nums[k], nums[j]
                else:
                    k = k + 1
            quick_sort(l, i)
            quick_sort(j, r)

        quick_sort(0, len(nums) - 1)
        return nums

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understand how divide-and-conquer strategies, like Merge Sort, Quick Sort, and Heap Sort, apply to the sorting problem.
question_mark
Test candidate's ability to balance time and space complexity considerations when choosing an algorithm.
question_mark
Look for the candidate's awareness of edge cases and their understanding of sorting algorithm stability and performance.

warning

常见陷阱

外企场景

error
Not considering the time and space complexity trade-offs for large input sizes.
error
Choosing Quick Sort without implementing it in a way that handles the worst-case time complexity properly.
error
Misunderstanding the problem's constraints and opting for a non-O(n log n) algorithm such as Bubble Sort or Insertion Sort.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sorting the array in descending order instead of ascending.
arrow_right_alt
Sorting an array with a custom comparison function for non-numeric values.
arrow_right_alt
Handling arrays with duplicate values and ensuring correct stability in the sorting algorithm.

help

常见问题

外企场景

继续练习

#347 前 K 个高频元素 #973 最接近原点的 K 个点 #692 前K个高频单词