【Day 36 】2024-05-13 - 912. 排序数组

[azl397985856]

912. 排序数组

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sort-an-array/

前置知识

• 数组
• 排序

  题目描述

  
  给你一个整数数组 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

[zhiyuanpeng]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) > 1:
            mid = len(nums)//2
            left = nums[:mid]
            right = nums[mid:]
            left = self.sortArray(left)
            right = self.sortArray(right)
            ans = self.merge(left, right)
            return ans
        else:
            return nums

    def merge(self, left, right):
        ans = []
        l,r = 0,0
        while l < len(left) and r < len(right):
            if left[l] <= right[r]:
                ans.append(left[l])
                l += 1
            else:
                ans.append(right[r])
                r += 1
        while l < len(left):
            ans.append(left[l])
            l += 1
        while r < len(right):
            ans.append(right[r])
            r += 1
        return ans 

[luzhaofeng]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quickSort(nums, 0, len(nums)-1)
        return nums

    def quickSort(self, nums, left: int, right: int):
        flag = nums[randint(left, right)]
        i,j = left,right

        while i<=j:
            while nums[i]<flag:
                i+=1
            while nums[j]>flag:
                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 left<j:
            self.quickSort(nums, left, j)

[Yukibei]

class Solution { public: vector sortArray(vector& nums) { sort(nums.begin(),nums.end()); return nums; } ｝； 时间复杂度n 空间复杂度n

[hillsonziqiu]

思路

快排

代码

/*
 * @lc app=leetcode.cn id=912 lang=javascript
 *
 * [912] 排序数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  if (nums.length <= 1) {
    return nums;
  }

  // 获取中点下标
  const midIdx = Math.floor(nums.length / 2);

  // 获取中点元素
  const mid = nums[midIdx];
  const left = [];
  const right = [];

  // 遍历数组，将小于中点的元素放入left数组，大于中点的元素放入right数组
  for (let i = 0; i < nums.length; i++) {
    if (i === midIdx) continue;
    if (nums[i] < mid) {
      left.push(nums[i]);
    } else {
      right.push(nums[i]);
    }
  }

  return [...sortArray(left), mid, ...sortArray(right)];
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn) ~ O(n^2) 空间复杂度：O(log n) ~ O(n)

[Lizhao-Liu]

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
      let min = nums.min()!
      let max = nums.max()!

      var countArr = [Int](repeating: 0, count: max - min + 1)
      for num in nums {
        countArr[num-min] += 1
      }

      var res = [Int]()
      for i in 0..<countArr.count {
        if countArr[i] == 0 {
          continue
        }
        for _ in 0..<countArr[i] {
          res.append(i+min)
        }
      }
      return res
    }
}

[xil324]

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return nums

        mid = len(nums) // 2
        left = nums[:mid]
        right = nums[mid:]
        self.sortArray(left)
        self.sortArray(right)
        first = 0
        second = 0
        curr = 0
        while first < len(left) and second < len(right):
            if left[first] <= right[second]:
                nums[curr] = left[first]
                first += 1
            else:
                nums[curr] = right[second]
                second += 1
            curr += 1
        while first < len(left):
            nums[curr] = left[first]
            curr+=1
            first += 1
        while second < len(right):
            nums[curr] = right[second]
            second += 1
            curr += 1
        return nums

[Dtjk]

class Solution { public: vector sortArray(vector& nums) { heapSort(nums); return nums; } void maxHeapify(vector& nums, int i, int length) { while (2 i + 1 < length){ int min_index = i; if (2 i + 1 < length && nums[2 i + 1] > nums[min_index]) min_index = 2 i + 1; if (2 i + 2 < length && nums[2 i + 2] > nums[min_index]) min_index = 2 * i + 2; if (min_index == i) break; swap(nums[min_index], nums[i]); i = min_index; } } void heapSort(vector& nums) { for (int i = (nums.size() >> 1) - 1; i >= 0; i--) maxHeapify(nums, i, nums.size()); int end = nums.size(); while(--end > 0) { swap(nums[0], nums[end]); maxHeapify(nums, 0, end); } } };

[GReyQT]

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        mergeSort(nums, 0, n - 1);
        return nums;
    }
    // 归并排序
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    // 合并两个有序数组
    void merge(vector<int>& nums, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        vector<int> L(n1), R(n2);
        for (int i = 0; i < n1; ++i)
            L[i] = nums[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = nums[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                nums[k++] = L[i++];
            } else {
                nums[k++] = R[j++];
            }
        }
        while (i < n1) {
            nums[k++] = L[i++];
        }
        while (j < n2) {
            nums[k++] = R[j++];
        }
    }
};

[CathyShang]

冒泡，计数

class Solution:
    # def swp(self, nums:List[int], a:int, b:int):
    #     temp = nums[a]
    #     nums[a] = nums[b]
    #     nums[b] = temp

    def sortArray(self, nums: List[int]) -> List[int]:
        # # 冒泡
        # n = len(nums)
        # flag = 1
        # for i in range(n-1):
        #     for j in range(0,n-i-1):
        #         if(nums[j]>nums[j+1]):
        #             self.swp(nums, j, j+1)
        #             flag = 0
        #     if(flag):break

        # return nums
        n = len(nums)
        min_m = min(nums)
        max_m = max(nums)
        cout = [0]*(max_m-min_m+1)
        for i in range(n):
            cout[nums[i]-min_m] +=1
        cur = 0
        for j in range(max_m-min_m+1):
            while(cout[j]):
                nums[cur] = j + min_m
                cout[j] += -1
                cur += 1
        return nums

计数复杂度满足

• Time O(Max-Min)
• Space O(Max-Min)