Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 912. Sort an Array

leetcode
tags: leetcode

問題

整数の配列numsを受け取った時, 降順に配列を整列せよ

制約: $$ |nums| \in [1, 50000] $$

$$ nums[i] \in [-50000, 50000] $$

解法

色々な解法が考えられます.

この問題が"Recursion"の一種として取り上がられているので再帰的な手法で解きます

divide-conquer

有名な再帰的なソート手法にMerge Sortがあります

これはdivide-conquerという手法を使ったアルゴリズムです

これは日本語だと分割統治法と呼ばれ, 問題を分割し, 細分化され単純化された問題を統合するという方法です

Merge Sortは配列を小さな配列に分割して, それらを整列させ統合させます

以下のように

  • 配列を分割します
    • 分割した配列同士を組み合わせます
    • 組み合わせる際に分割した2つの配列の中から小さい要素を組み合わせて新しい配列を返します
  • 基底は配列の大きさが$1$であるときです

計算量

与えられる配列の長さを$n$とします

  • 空間計算量は分割するごとに新しく$n$の配列を2つ作る必要があるので$O(n \log(n))$
    • これについては詳しく時間計算量の方を参照
  • 時間計算量は毎回の配列を並べ替えるのに$O(n)$が必要な操作を$O(\log(n))$回する必要があり, 全て合わせて$O(n \log(n))$
    • なぜ$O(\log(n))$回なのかは1回で配列が2倍になるのでx回の操作で$2^{x} = n$となります
    • 底が$2$である対数を両辺から取ると$x = \log(n)$となり, この$O(\log(n))$の計算量が必要な分割を1回し, 同じ計算量の統治を1回します

Python

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
      l = len(nums)
      self.mergeSort(nums, 0, l)
      return nums
        
    def merge(self, arr, left, mid, right):
      n1 = mid - left
      n2 = right - mid
      L = [arr[left + i] for i in range(n1)]
      R = [arr[mid + i] for i in range(n2)]
      L.append(float('inf'))
      R.append(float('inf'))
      ri, li = 0, 0
      for ai in range(left, right):
        if L[li] <= R[ri]:
          arr[ai] = L[li]
          li += 1
        else:
          arr[ai] = R[ri]
          ri += 1
        
    def mergeSort(self, arr, left, right):
      if left + 1 < right:
        mid = (left + right) // 2
        self.mergeSort(arr, left, mid)
        self.mergeSort(arr, mid, right)
        self.merge(arr, left, mid, right)

C++

class Solution {
public:
  vector<int> sortArray(vector<int>& nums) {
    mergeSort(nums, 0, nums.size());
    return nums;
  }
  
private:
  void mergeSort(vector<int>& arr, int left, int right) {
    if (left + 1 < right) {
      int mid = (left + right) / 2;
      mergeSort(arr, left, mid);
      mergeSort(arr, mid, right);
      merge(arr, left, mid, right);
    }
  }
  void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    vector<int> L(n1 + 1), R(n2 + 1);
    for (int i = 0; i < n1; i++) {
      L[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
      R[i] = arr[mid + i];
    }
    L[n1] = R[n2] = INT_MAX;
    int ri = 0, li = 0;
    for (int ai = left; ai < right; ai++) {
      if (L[li] <= R[ri]) {
        arr[ai] = L[li];
        li++;
      } else {
        arr[ai] = R[ri];
        ri++;
      }
    }
  }
};