912. Sort an Array

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #recursion #sort #two-pointers

LeetCode Static

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

Input: nums = [5,2,3,1]

Output: [1,2,3,5]

C# решение

сопоставлено/оригинал

using System;
class Program {
    static void MergeSort(int[] nums) {
        if (nums.Length > 1) {
            int mid = nums.Length / 2;
            int[] left_half = new int[mid];
            int[] right_half = new int[nums.Length - mid];
            Array.Copy(nums, 0, left_half, 0, mid);
            Array.Copy(nums, mid, right_half, 0, nums.Length - mid);
            MergeSort(left_half);
            MergeSort(right_half);
            int i = 0, j = 0, k = 0;
            while (i < left_half.Length && j < right_half.Length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }
            while (i < left_half.Length) {
                nums[k++] = left_half[i++];
            }
            while (j < right_half.Length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Program {
    static void MergeSort(vector<int>& nums) {
        if (nums.size() > 1) {
            int mid = nums.size() / 2;
            vector<int>& left_half = new int[mid];
            vector<int>& right_half = new int[nums.size() - mid];
            Array.Copy(nums, 0, left_half, 0, mid);
            Array.Copy(nums, mid, right_half, 0, nums.size() - mid);
            MergeSort(left_half);
            MergeSort(right_half);
            int i = 0, j = 0, k = 0;
            while (i < left_half.size() && j < right_half.size()) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }
            while (i < left_half.size()) {
                nums[k++] = left_half[i++];
            }
            while (j < right_half.size()) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

Java решение

сопоставлено/оригинал

import java.util.Arrays;

public class Main {
    public static void mergeSort(int[] nums) {
        if (nums.length > 1) {
            int mid = nums.length / 2;
            int[] left_half = Arrays.copyOfRange(nums, 0, mid);
            int[] right_half = Arrays.copyOfRange(nums, mid, nums.length);

            mergeSort(left_half);
            mergeSort(right_half);

            int i = 0, j = 0, k = 0;
            while (i < left_half.length && j < right_half.length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }

            while (i < left_half.length) {
                nums[k++] = left_half[i++];
            }

            while (j < right_half.length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

JavaScript решение

сопоставлено/оригинал

function mergeSort(nums) {
    if (nums.length <= 1) {
        return nums;
    }

    const mid = Math.floor(nums.length / 2);
    const left = mergeSort(nums.slice(0, mid));
    const right = mergeSort(nums.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

Python решение

сопоставлено/оригинал

def mergeSort(nums):
    if len(nums) > 1:
        mid = len(nums) // 2
        left_half = nums[:mid]
        right_half = nums[mid:]

        mergeSort(left_half)
        mergeSort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                nums[k] = left_half[i]
                i += 1
            else:
                nums[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            nums[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            nums[k] = right_half[j]
            j += 1
            k += 1

    return nums

Go решение

сопоставлено/оригинал

package main

import (
    "fmt"
)

func mergeSort(nums []int) {
    if len(nums) > 1 {
        mid := len(nums) / 2
        left_half := make([]int, mid)
        right_half := make([]int, len(nums)-mid)

        copy(left_half, nums[:mid])
        copy(right_half, nums[mid:])

        mergeSort(left_half)
        mergeSort(right_half)

        i, j, k := 0, 0, 0
        for i < len(left_half) && j < len(right_half) {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i++
            } else {
                nums[k] = right_half[j]
                j++
            }
            k++
        }

        for i < len(left_half) {
            nums[k] = left_half[i]
            i++
            k++
        }

        for j < len(right_half) {
            nums[k] = right_half[j]
            j++
            k++
        }
    }
}

Algorithm

Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

Разделить массив на две половины.

Рекурсивно отсортировать каждую половину.

Слить две отсортированные половины.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.