LeetCode 补充题 15. 自然数数组的排序

Categories:

题目描述
思路分析
1. 解法一：计数排序（推荐）
2. 解法二：原地置换（元素是 0..n-1 且互不相同）
相似题目

题目描述

✅ 补充题 15. 自然数数组的排序

思路分析

解法一：计数排序（推荐）

核心思路：

自然数数组可以用计数排序：统计每个数出现次数，再按数值顺序回填。

先扫描数组得到最大值，申请计数数组。

依次输出每个数的出现次数。

复杂度分析：

时间复杂度：O(n + m)，其中 n 表示数组长度，m 为最大值。

空间复杂度：O(m)，计数数组。

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int[] cnt = new int[max + 1];
        for (int num : nums) {
            cnt[num]++;
        }

        int idx = 0;
        for (int num = 0; num <= max; num++) {
            while (cnt[num] > 0) {
                nums[idx++] = num;
                cnt[num]--;
            }
        }

        return nums;
    }
}

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	maxVal := 0
	for _, num := range nums {
		if num > maxVal {
			maxVal = num
		}
	}

	cnt := make([]int, maxVal+1)
	for _, num := range nums {
		cnt[num]++
	}

	idx := 0
	for num := 0; num <= maxVal; num++ {
		for cnt[num] > 0 {
			nums[idx] = num
			idx++
			cnt[num]--
		}
	}

	return nums
}

解法二：原地置换（元素是 0..n-1 且互不相同）

核心思路：

若数组包含 0..n-1 且互不相同，可将元素交换到其对应下标。

当 nums[i] != i 时，与 nums[nums[i]] 交换直到归位。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public void sortPermutation(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                int next = nums[i];
                int tmp = nums[i];
                nums[i] = nums[next];
                nums[next] = tmp;
            }
        }
    }
}

func sortPermutation(nums []int) {
	for i := 0; i < len(nums); i++ {
		for nums[i] != i {
			next := nums[i]
			nums[i], nums[next] = nums[next], nums[i]
		}
	}
}

相似题目

题目	难度	考察点
912. 排序数组	中等	排序
75. 颜色分类	中等	计数/双指针
1122. 数组的相对排序	简单	计数排序
1051. 高度检查器	简单	计数排序
41. 缺失的第一个正数	困难	原地置换

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/53157769