当前位置: 首页 > web >正文

LeetCode算法日记 - Day 24: 颜色分类、排序数组

目录

1. 颜色分类

1.1 题目分析

1.2 解法

1.3 代码实现

2. 排序数组

2.1 题目解析

2.2 解法

2.3 代码实现


1. 颜色分类

75. 颜色分类 - 力扣(LeetCode)

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

    必须在不使用库内置的 sort 函数的情况下解决这个问题。

    示例 1:

    输入:nums = [2,0,2,1,1,0]
    输出:[0,0,1,1,2,2]
    

    示例 2:

    输入:nums = [2,0,1]
    输出:[0,1,2]

    提示:

    • n == nums.length
    • 1 <= n <= 300
    • nums[i] 为 01 或 2

    1.1 题目分析

    题目本质
    只有三种取值 0/1/2,要求原地按 0→1→2 排序。可抽象为:一次扫描把元素分到三个“桶/分区”。

    常规解法

    • 计数法:统计 0/1/2 的数量,再回写。时间 O(n),空间 O(1),两趟且缺少“原地一次遍历”的训练价值。

    • 直接排序:不允许用库排序,且会是 O(n log n)。

    问题分析
    若用交换排序或冒泡都会超过 O(n)。想在 O(n) 一趟里完成,必须让每次访问都把当前元素“扔到正确区域”,并保持区间边界稳定(循环不变式),这就是“荷兰国旗”思想。

    思路转折
    维护三指针把数组动态分成 4 段(不变式):

    • 0..left-1 全是 0

    • left..i-1 全是 1

    • i..right 还未处理

    • right+1..n-1 全是 2
      指针 i 扫描未处理区:遇到 0 扔到左边,遇到 2 扔到右边,遇到 1 跳过。直到 i > right 结束

    1.2 解法

    算法思想

    三指针分区(Dutch National Flag):

    • ↦ 与 left 交换,left++,i++

    • 1 ↦ i++

    • 2 ↦ 与 right 交换,right--,i 不动(因为换来的元素未检查)

    i)初始化:left=0, right=n-1, i=0。

    ii)循环 i <= right:

    • nums[i]==0:交换到左区,扩左界并前进 i;

    • nums[i]==2:交换到右区,收缩右界,但不移动 i;

    • nums[i]==1:仅 i++。

    iii)循环结束时四段不变式成立,数组即为 0…0 1…1 2…2。

    小解释:为什么 0 情况可以 i++,而 2 情况不能

    • 0 情况:left 永远 ≤ i。交换把 0 放到最左侧,nums[i] 会变成原来 left 位置的元素(已处理区的 1),可以直接前进。

    • 2 情况:right 在 i 右边,交换把一个未知元素换到 i,必须继续判断它,所以 不能 i++

    1.3 代码实现

    代码实现(写法一:直观边界 i <= right)

    class Solution {private void swap(int[] a, int i, int j) {int t = a[i]; a[i] = a[j]; a[j] = t;}public void sortColors(int[] nums) {int n = nums.length;int left = 0, right = n - 1; // 左右“投放位”for (int i = 0; i <= right; ) {if (nums[i] == 0) {swap(nums, left, i);left++; i++;             // 换来的一定在[0,left)或[1区],无需再查} else if (nums[i] == 2) {swap(nums, right, i);right--;                 // 换来的未知,i不动,继续检查当前位置} else { // nums[i] == 1i++;}}}
    }
    

    代码实现(写法二:i < right,left=-1,right=n)

    class Solution {private void swap(int[] a, int i, int j) {int t = a[i]; a[i] = a[j]; a[j] = t;}public void sortColors(int[] nums) {int left = -1, right = nums.length, i = 0;while (i < right) {if (nums[i] == 0)       swap(nums, ++left, i++); // 左区扩张else if (nums[i] == 1)  i++;                     // 中区自然累积else                    swap(nums, --right, i);  // 右区收缩,i不动}}
    }
    

    复杂度分析

    • 时间复杂度:O(n)(每个元素最多被交换/访问常数次)

    • 空间复杂度:O(1)(原地修改,仅常数指针)

    2. 排序数组

    912. 排序数组 - 力扣(LeetCode)

    给你一个整数数组 nums,请你将该数组升序排列。

    你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。

      示例 1:

      输入:nums = [5,2,3,1]
      输出:[1,2,3,5]
      解释:数组排序后,某些数字的位置没有改变(例如,2 和 3),而其他数字的位置发生了改变(例如,1 和 5)。
      

      示例 2:

      输入:nums = [5,1,1,2,0,0]
      输出:[0,0,1,1,2,5]
      解释:请注意,nums 的值不一定唯一。

      提示:

      • 1 <= nums.length <= 5 * 104
      • -5 * 104 <= nums[i] <= 5 * 104

      2.1 题目解析

      题目本质
      把整型数组升序排列;目标是平均 O(n log n),并尽量原地。数据范围允许重复与负数。

      常规解法

      • 归并排序:时间稳定 O(n log n),但需要 O(n) 额外空间。

      • 快速排序:平均 O(n log n)、原地;若选取随机基准 + 三路划分,对大量重复值更友好。

      问题分析

      • 经典双路快排在重复元素多时会退化,划分不均,递归层次加深。

      • 三路划分把数组维护为三段:< key、= key、> key,一次扫描就把等于段“压缩”出来,递归只落在两侧,更稳定。

      思路转折(不变式引导)
      在子数组 [l, r] 内维护指针 left/i/right,保持不变式:

      • [l, left] < key

      • [left+1, i-1] = key

      • [i, rgiht-1] 未处理

      • [right, r] > key

      • 循环扫描未处理区:
        a[i] < key → 交换到左边 swap(++lt, i++)
        a[i] == key→ i++
        a[i] > key→ 交换到右边 swap(--gt, i)(i 不动,因新换来的还未判断)
        当 i == right,未处理区为空,递归排序 < key的 [l,left] 与 > key的 [right, r] 两端。

      2.2 解法

      算法思想

      • 随机基准:降低恶劣输入导致的退化概率;

      • 三路划分:一次扫描把等于段“吃掉”,递归只落两端;

      • 原地交换:常数额外空间。

      i)递归基:if (l >= r) return;

      ii)选择基准:key= nums[new Random().nextInt(r-l+1) + l]

      iii)运行三路划分循环,维持不变式。

      iiii)递归处理 [l, lt] 与 [gt, r]。

      iiiii)结束

      容易踩坑点:

      • 比较方向:a[i] < key 放左边;a[i] > key 放右边

      • 递归基:if (l >= r) return;

      • i 的移动:放左 i++;放右 不要 i++;等于 i++。

      • 边界名分清:l/r(递归区间)
        l / r:当前递归处理的子数组边界(闭区间)。
        left/right/i:划分指针,lt = l-1, i = l, gt = r+1

      • key:数值(从 [l, r] 随机取出的元素的值);不是索引。 复杂度分析

      2.3 代码实现

      import java.util.concurrent.ThreadLocalRandom;class Solution {private void swap(int[] a, int i, int j) {int t = a[i]; a[i] = a[j]; a[j] = t;}public int[] sortArray(int[] nums) {qsort(nums, 0, nums.length - 1);return nums;}private void qsort(int[] nums, int l, int r) {if (l >= r) return; // 递归基// 随机基准,降低退化概率int key = nums[new Random().nextInt(r-l+1) + l];int left = l - 1, i = l, right = r + 1;// 不变式:// [l, left]     < key// [left+1, i-1] = key// [i, right-1]   未处理// [right, r]     > keywhile (i < right) {if (nums[i] < key ) {swap(nums, ++left, i++);} else if (nums[i] > key ) {swap(nums, --right, i);   // i 不动:换来的还未检查} else {i++;}}// 递归两端;等于 key 的中段 [left+1, right-1] 已就位qsort(nums, l, left);qsort(nums, right, r);}
      }
      

      复杂度分析

      • 时间复杂度:期望 O(n log n);最差 O(n^2)(随机化可将概率降到极低)。

      • 空间复杂度:原地划分 O(1) 额外空间,整体为递归栈 O(log n)(期望)

      http://www.xdnf.cn/news/19064.html

      相关文章:

    1. PyTorch图像预处理完全指南:从基础操作到GPU加速实战
    2. 完整实验命令解析:从集群搭建到负载均衡配置(2)
    3. [vcpkg] Windows入门使用介绍
    4. day22 回溯算法part01
    5. 服务器类型与TCP并发服务器构建(SELECT)
    6. 设计模式:桥接模式(Bridge Pattern)
    7. 《Linux内存管理:实验驱动的深度探索》【附录】【实验环境搭建 7】【使用buildroot方式构建文件系统】
    8. 【开发便利】让远程Linux服务器能够访问内网git仓库
    9. 链表-25.k个一组翻转链表-力扣(LeetCode)
    10. 深入解析 Flink Function
    11. Vue将内容生成为二维码,并将所有二维码下载为图片,同时支持批量下载(下载为ZIP),含解决一次性生成过多时页面崩溃解决办法
    12. TCP 并发服务器构建
    13. 智芯MCU 勘误文档问题解析
    14. 【Java知识】Java线程相关对象全面解析与最佳实践
    15. 阿里云——应用交付与负载均衡
    16. 数据对话的“通用语法”:SQL与KingbaseES的智能处理艺术
    17. 从感知机到大模型:神经网络的全景解析与实践指南
    18. ES01-环境安装
    19. 盛大启幕!融智兴科技亮相 IOTE 2025 深圳国际物联网展
    20. SegEarth-R1: Geospatial Pixel Reasoning via Large Language Model
    21. 稀土:从“稀有”到“命脉”的科技核心
    22. LeetCode算法日记 - Day 23: 外观数列、数青蛙
    23. LeetCode - 155. 最小栈
    24. 8.28 模拟
    25. rust语言(1.88.0)sqlite数据库rusqlite库(0.37.0)学习笔记
    26. 蘑兔音乐:帮你把灵感落地
    27. 【新版发布】Apache DolphinScheduler 3.3.1 正式上线:更稳、更快、更安全!
    28. 【Django + Pure Admin】基于Django+Vue3的前后端分离管理系统框架设计
    29. 预处理详解
    30. 【Spring Cloud 微服务】5.架构的智慧枢纽:深度剖析 Nacos 注册中心