LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.08
• 题目：2161. 根据给定数字划分数组
• 难度：中等
• 标签：数组、双指针

1. 题目理解

问题描述： 给定数组 nums 和一个整数 pivot，将数组重新排列，使得：

1. 所有小于 pivot 的元素出现在最前面；
2. 所有等于 pivot 的元素出现在中间；
3. 所有大于 pivot 的元素出现在最后；
4. 同时保持小于、大于 pivot 的元素之间的相对顺序不变。

示例：

输入：nums = [9,12,5,10,14,3,10], pivot = 10 输出：[9,5,3,10,10,12,14]

2. 解题思路

核心观察

• 问题可以拆解为三个部分：小于 pivot、等于 pivot、大于 pivot。
• 为了保持相对顺序，遍历一次数组分别收集三类元素，再按顺序拼接即可。
• 优化方案：使用双指针一次遍历完成填充，最后反转大于 pivot 的部分，保证其相对顺序。

算法步骤

1. 初始化结果数组，并全部填充为 pivot；
2. 双指针 left 和 right 分别从两端开始：
   • 遍历原数组，遇到小于 pivot 的元素放到 left 位置；
   • 遇到大于 pivot 的元素放到 right 位置；
3. 遍历结束后，反转 right 之后的部分，恢复大于 pivot 元素的原始顺序；
4. 返回结果数组。

3. 代码实现

package lc2161;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int[] pivotArray(int[] nums, int pivot) {
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < pivot) {
                q1.add(nums[i]);
            } else if (nums[i] == pivot) {
                count++;
            } else {
                q2.add(nums[i]);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (!q1.isEmpty()) {
                nums[i] = q1.poll();
                continue;
            }
            if (count != 0) {
                nums[i] = pivot;
                count--;
                continue;
            }
            if (!q2.isEmpty()) {
                nums[i] = q2.poll();
            }
        }
        return nums;
    }
}

4. 代码优化说明

class Solution {
public int[] pivotArray(int[] nums, int pivot) {
    int n = nums.length;
    int[] ans = new int[n];
    // 先将结果数组全部填充为pivot，中间部分直接就位
    Arrays.fill(ans, pivot);
    // left指针从左往右放小于pivot的元素
    // right指针从右往左放大于pivot的元素
    int left = 0, right = n - 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] < pivot) {
            ans[left] = nums[i];
            left++;
        } else if (nums[i] > pivot) {
            ans[right] = nums[i];
            right--;
        }
    }
    // 反转右侧大于pivot的部分，恢复其原始顺序
    reverse(ans, right + 1, n - 1);
    return ans;
}

    private void reverse(int[] arr, int left, int right) {
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

5. 复杂度分析

• 队列实现版
  • 时间复杂度：$O(n)$，两次线性遍历。
  • 空间复杂度：$O(n)$，两个队列存储元素。
• 双指针优化版
  • 时间复杂度：$O(n)$，一次遍历+一次反转。
  • 空间复杂度：$O(n)$，结果数组的必要开销，无额外队列空间。

6. 总结

• 核心：分区+保持相对顺序，是稳定划分的典型问题。
• 优化亮点：
  1. 利用 Arrays.fill 直接就位中间的 pivot 元素；
  2. 双指针一次遍历完成左右填充，无需额外队列；
  3. 反转操作恢复右侧元素的原始顺序，逻辑清晰高效。
• 关键技巧：先从两端填充，再反转恢复顺序，减少了额外空间开销。ss