LeetCode 912. 排序数组

简介: 给你一个整数数组 nums,请你将该数组升序排列。

网络异常,图片无法展示
|

题目地址(912. 排序数组)

leetcode-cn.com/problems/so…

题目描述

给你一个整数数组 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 <= 50000
-50000 <= nums[i] <= 50000

思路

快速排序,pivot随机主元通过,固定位置容易超时

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # # 超时
        # if len(nums) <= 1:
        #     return nums
        # pivot = nums[0]
        # right,left = [],[]
        # for each in nums[1:]:
        #     if each <= pivot:
        #         left.append(each)
        #     else:
        #         right.append(each)
        # return self.sortArray(left) + [pivot] + self.sortArray(right)
        # 快速排序,采用随机pivot
        from random import randint
        if len(nums) <= 1:
            return nums
        randNum = randint(0,len(nums)-1)
        pivot = nums[randNum]
        right, left = [], []
        for index,each in enumerate(nums):
            if index == randNum:continue
            if each <= pivot:
                left.append(each)
            else:
                right.append(each)
        return self.sortArray(left) + [pivot] + self.sortArray(right)
    #     #快速排序
    #     self.quickSort(nums,0,len(nums)-1)
    #     return nums
    #
    # def quickSort(self, nums, left, right):
    #     from random import randint
    #     pivot = nums[randint(left,right)]
    #     i,j = left, right
    #     while i<=j:
    #         # print(i,j,nums)
    #         while nums[i]<pivot:
    #             i += 1
    #         while nums[j]>pivot:
    #             j -= 1
    #         if i<=j:
    #             nums[i],nums[j] = nums[j],nums[i]
    #             i += 1
    #             j -= 1
    #     if i < right:
    #         self.quickSort(nums, i, right)
    #     if j > left:
    #         self.quickSort(nums,left, j)
if __name__ == '__main__':
    nums = [5,1,1,2,0,0]
    ret = Solution().sortArray(nums)
    print(ret)

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(logn)O(logn)
  • 空间复杂度:O(logn)O(logn)
目录
打赏
0
0
0
0
1
分享
相关文章
|
5月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
64 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
40 4
|
5月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
43 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
5月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
98 0
|
5月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
35 0
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等