912. Sort an Array - 排序数组

Tags - 题目标签

Description - 题目描述

EN:

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

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

ZH-CN:

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	160 ms	55.7 MB	2021/04/05 0:23

// 一趟快排的结果，返回结果和枢轴位置
const partition = (arr: number[]): [number[], number] => {
  const pivot = arr[0];
  const left = arr.filter(e => e < pivot);
  const pivotIdx = left.length;
  let hasSameFlag: boolean = false;
  const right = arr.filter(e => {
    if (e === pivot) {
      if (!hasSameFlag) {
        hasSameFlag = true;
        return false;
      } else {
        return true;
      }
    } else {
      return e >= pivot;
    }
  });
  return [[...left, pivot, ...right], pivotIdx];
}

const quickSort = (arr: number[]): number[] => {
  if (arr.length === 0) {
    return arr;
  }
  const [res, pivotIdx] = partition(arr);
  const pivot = res[pivotIdx];
  const left = quickSort(res.slice(0, pivotIdx));
  const right = quickSort(res.slice(pivotIdx + 1));
  return [...left, pivot, ...right];
}


function sortArray(nums: number[]): number[] {
  return quickSort(nums);
};

My Notes - 我的笔记

先上经典解法

// 一趟快排的划分（原地工作，改变数组）
const partition = (arr: number[], start: number, end: number): number => {
  // 选取第一个数字下标作为枢轴
  const pivotIdx = start;
  // 缓存枢轴上的数字
  const pivot = arr[pivotIdx];

  let startPtr = start;
  let endPtr = end;

  while (startPtr < endPtr) {
    while(arr[endPtr] >= pivot && startPtr < endPtr) {
      endPtr--;
    }

    arr[startPtr] = arr[endPtr];

    while(arr[startPtr] <= pivot && startPtr < endPtr) {
      startPtr++;
    }
    arr[endPtr] = arr[startPtr];
  }
  arr[startPtr] = pivot;
  return startPtr;
}

// 原地工作的快排算法
const quickSortInner = (nums: number[], start: number = 0, end: number = nums.length - 1): number[] => {
  if (start >= end) {
    return nums;
  }
  const pivotIdx = partition(nums, start, end);
  quickSortInner(nums, start, pivotIdx - 1);
  quickSortInner(nums, pivotIdx + 1, end);
}

const quickSort = (nums: number[]): number[] => {
  const numsCopy = [...nums];
  quickSortInner(numsCopy);
  return numsCopy;
};

function sortArray(nums: number[]): number[] {
  return quickSort(nums);
};

partition

原地的快速排序是赋值，而不是交换。当两个指针重合后，最终要把枢轴赋给该位置。移动时，还要注意两个指针是否重合了。如果选择第一个位置为枢轴，必须从高位开始。当等于时，必须跳过而不是交换。区分 pivot 和 pivotIdx。

quickSortInner

由于是原地启动的快排，相当于改变了参数，所以不能这样写：

const quickSort = (nums: number[], start: number = 0, end: number = nums.length - 1): number[] => {
	if (start >= end) {
    return nums;
  }
  const copy = [...nums];
  const pivotIdx = partition(nums, start, end);
  quickSortInner(nums, start, pivotIdx - 1);
  quickSortInner(nums, pivotIdx + 1, end);
  return copy;
};

因为调用栈永远保存是第一趟排序的结果，所以 copy 总是第一趟排序的结果。注意加上停止递归的条件：

if (start >= end) {
  return nums;
}

易于理解的方法

/**
 * 一趟快排的结果，返回结果和枢轴位置
 *  @params arr: number[] 原始数组
 *  @returns [number[], number] 一趟快排后的数组和枢轴位置
 */
const partition = (arr: number[]): [number[], number] => {
  const pivot = arr[0];
  const left = arr.filter(e => e < pivot);
  const pivotIdx = left.length;
  let hasSameFlag: boolean = false;
  const right = arr.filter(e => {
    // 当第一次遇到值和枢轴相同的元素，不将其加入 right，否则会重复
    if (e === pivot) {
      if (!hasSameFlag) {
        hasSameFlag = true;
        return false;
      } else {
        return true;
      }
    } else {
      return e >= pivot;
    }
  });
  return [[...left, pivot, ...right], pivotIdx];
}

const quickSort = (arr: number[]): number[] => {
  if (arr.length === 0) {
    return arr;
  }
  const [res, pivotIdx] = partition(arr);
  const pivot = res[pivotIdx];
  const left = quickSort(res.slice(0, pivotIdx));
  const right = quickSort(res.slice(pivotIdx + 1));
  return [...left, pivot, ...right];
}


function sortArray(nums: number[]): number[] {
  return quickSort(nums);
};

FilesExpand file tree

sort-an-array.md

Latest commit

History