数组

随机数

// #include <cstdlib>
// #include <ctime>

// srand(time(0));
// int x = rand() % 100;
// // 生成 [a, b] 之间的随机数
// int a = 10, b = 20;
// int r = a + rand() % (b - a + 1);

// C++11 及以上版本推荐使用 <random> 库来生成随机数
// #include <random>
// #include <chrono>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int r = uniform_int_distribution<int>(1, 100)(rng);

数组的基本性质

• 数组是存放在连续内存空间上的相同类型数据的集合
• 数组下标都是从0开始的
• 数组内存空间的地址是连续的
• 正是因为数组在内存空间的地址是连续的，所以在删除或者增添元素的时候，就必须要移动其他元素的地址——注意，数组的元素是不能直接删除的，只能覆盖
• 在 C++ 中，二维数组在内存的空间地址是连续的

排序

冒泡排序

• 冒泡排序是最基础的交换排序，核心思想是：

  • 重复遍历待排序的数组，两两比较相邻元素，如果顺序错误（如升序要求下前大后小）就交换它们
  • 每一轮遍历都会将当前未排序部分的最大元素 “冒泡” 到末尾
  • 当某一轮遍历中没有发生任何交换时，说明数组已完全有序，可提前终止，优化效率

• 升序排序

  #include <iostream>
  #include <vector>
  using namespace std;
  
  // 冒泡排序（升序）
  void bubbleSort(vector<int>& nums) {
      int n = nums.size();
      // 外层循环：控制排序轮数（最多n-1轮，因为最后一个元素无需再比较）
      for (int i = 0; i < n - 1; ++i) {
          bool swapped = false; // 标记本轮是否发生交换，优化
          // 内层循环：每轮比较到未排序的最后一个元素（已排序的在末尾，无需比较）
          for (int j = 0; j < n - 1 - i; ++j) {
              if (nums[j] > nums[j + 1]) { // 前大后小，交换
                  swap(nums[j], nums[j + 1]);
                  swapped = true;
              }
          }
          // 本轮无交换，说明数组已有序，直接退出
          if (!swapped) {
              break;
          }
      }
  }
  
  // 测试函数
  int main() {
      vector<int> nums = {5, 2, 9, 1, 5, 6};
      bubbleSort(nums);
      // 输出：1 2 5 5 6 9
      for (int num : nums) {
          cout << num << " ";
      }
      return 0;
  }

• 最好的情况（数组已有序）：优化后 $O(n)$，未优化 $O(n^2)$

• 最好的情况（数组逆序）：$O(n^2)$

• 空间复杂度：$O(1)$​，原地排序，只使用常数级额外空间

快速排序

• 快速排序是分治思想的经典应用，核心思想是：

  • 选基准（pivot）：从数组中选一个元素作为 “基准值”（常见选法：首元素、尾元素、中间元素、随机元素）；
  • 分区（partition）：遍历数组，将小于基准的元素放到基准左边，大于基准的放到右边，基准最终落在 “正确位置”（排序后它应在的位置）；
  • 递归处理：对基准左边和右边的子数组重复上述步骤，直到子数组长度为 1（天然有序）

• 升序，以首元素为基准

  #include <iostream>
  #include <vector>
  using namespace std;
  
  // 分区函数：返回基准元素的最终索引
  int partition(vector<int>& nums, int left, int right) {
      // 选左边界为基准（也可优化为随机选，避免最坏情况）
      int pivot = nums[left];
      int i = left, j = right;
      while (i < j) {
          // 从右往左找第一个小于基准的元素
          while (i < j && nums[j] >= pivot) {
              j--;
          }
          // 从左往右找第一个大于基准的元素
          while (i < j && nums[i] <= pivot) {
              i++;
          }
          // 交换这两个元素
          if (i < j) {
              swap(nums[i], nums[j]);
          }
      }
      // 将基准元素放到正确位置（i/j重合的位置）
      swap(nums[left], nums[i]);
      return i; // 返回基准索引
  }
  
  // 快速排序递归函数
  void quickSort(vector<int>& nums, int left, int right) {
      // 递归终止条件：子数组长度<=1
      if (left >= right) {
          return;
      }
      // 分区，得到基准索引
      int pivotIdx = partition(nums, left, right);
      // 递归排序左子数组
      quickSort(nums, left, pivotIdx - 1);
      // 递归排序右子数组
      quickSort(nums, pivotIdx + 1, right);
  }
  
  // 对外封装（简化调用）
  void quickSort(vector<int>& nums) {
      if (nums.empty()) return;
      quickSort(nums, 0, nums.size() - 1);
  }
  
  // 测试函数
  int main() {
      vector<int> nums = {5, 2, 9, 1, 5, 6};
      quickSort(nums);
      // 输出：1 2 5 5 6 9
      for (int num : nums) {
          cout << num << " ";
      }
      return 0;
  }

• 最好/平均情况：$O(n\log n)$

• 最坏情况（数组已有序 / 逆序，且选首 / 尾为基准）：$O(n^2)$（可以通过随机选基准避免最坏情况）

• 空间复杂度：$O(\log n)$（递归调用栈的空间），原地排序（无额外数组空间）

• 不稳定排序（相等元素的相对顺序可能改变）

• 基准选择：随机选基准（swap(nums[left], nums[left + rand() % (right - left + 1)])），避免最坏情况

• 简单实现

   void quickSort(vector<int> &arr, int low, int high)
  {
      // 终止条件
      if (l >= r)
          return;
      // 选择基准元素
      int mid = low + (high - low) / 2;
      int pivot = arr[mid];
      int i = low, j = high;
      // 分区
      while (i <= j)
      {
          while (arr[i] < pivot)
              i++;
          while (arr[j] > pivot)
              j--;
          if (i <= j)
          {
              swap(arr[i], arr[j]);
              i++;
              j--;
          }
      }
      // 递归排序左右子数组
      quickSort(arr, low, j);
      quickSort(arr, i, high);
  }

• 快速排序链表

  struct ListNode
  {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
  
  ListNode *quickSortList(ListNode *head)
  {
      // 终止条件: 链表为空或只有一个节点
      if (!head || !head->next)
          return head;
      // 选择基准元素
      ListNode *pivot = head;
      ListNode *leftDummy = new ListNode(0);
      ListNode *rightDummy = new ListNode(0);
      ListNode *leftTail = leftDummy;
      ListNode *rightTail = rightDummy;
      ListNode *current = head->next;
  
      // 分区
      while (current)
      {
          if (current->val < pivot->val)
          {
              leftTail->next = current;
              leftTail = leftTail->next;
          }
          else
          {
              rightTail->next = current;
              rightTail = rightTail->next;
          }
          current = current->next;
      }
  
      // 递归排序左右子链表
      leftTail->next = nullptr;  // 断开左链表
      rightTail->next = nullptr; // 断开右链表
  
      ListNode *sortedLeft = quickSortList(leftDummy->next);
      ListNode *sortedRight = quickSortList(rightDummy->next);
  
      // 合并结果
      if (sortedLeft)
      {
          ListNode *tail = sortedLeft;
          while (tail->next)
              tail = tail->next;     // 找到左链表的尾部
          tail->next = pivot;        // 将基准元素连接到左链表的尾部
          pivot->next = sortedRight; // 将右链表连接到基准元素的后面
          return sortedLeft;         // 返回排序后的链表头部
      }
      else
      {
          pivot->next = sortedRight; // 将右链表连接到基准元素的后面
          return pivot;              // 返回基准元素作为排序后的链表头部
      }
  }

• 快速选择

  void quickSelect(vector<int> &arr, int low, int high, int k)
  {
      // 终止条件
      if (l >= r)
          return;
      // 选择基准元素
      int mid = low + (high - low) / 2;
      int pivot = arr[mid];
      int i = low, j = high;
      // 分区
      while (i <= j)
      {
          while (arr[i] < pivot)
              i++;
          while (arr[j] > pivot)
              j--;
          if (i <= j)
          {
              swap(arr[i], arr[j]);
              i++;
              j--;
          }
      }
      // 根据 k 的位置递归选择
      if (k <= j)
          quickSelect(arr, low, j, k);
      else if (k >= i)
          quickSelect(arr, i, high, k);
  }

插入排序

• 把数组分为两个区域：

  • 已排序区：初始时只有数组第一个元素（下标 0）；
  • 未排序区：从下标 1 开始的所有元素

• 排序过程（以升序为例）：

  1. 从未排序区取出第一个元素（记为 current），作为 “待插入元素”；

  2. 从已排序区的末尾向前遍历，依次比较 current

     和已排序区的元素：

     • 如果已排序区的元素 > current，则将该元素后移一位（为 current 腾出位置）；
     • 如果已排序区的元素 ≤ current，停止遍历（找到插入位置）；

  3. 将 current 插入到找到的位置；

  4. 重复步骤 1-3，直到未排序区为空

• 代码实现

  #include <iostream>
  #include <vector>
  using namespace std;
  
  /**
   * 插入排序（升序）
   * @param nums 待排序的数组（引用传递，直接修改原数组）
   */
  void insertionSort(vector<int>& nums) {
      // 获取数组长度，空数组或单元素数组无需排序
      int n = nums.size();
      if (n <= 1) return;
  
      // 外层循环：遍历未排序区（从第2个元素开始，下标1）
      for (int i = 1; i < n; ++i) {
          // 1. 取出未排序区的第一个元素作为待插入元素
          int current = nums[i];
          // j：已排序区的末尾索引，初始为i-1
          int j = i - 1;
  
          // 2. 向前遍历已排序区，找插入位置
          // 条件：j>=0（不越界）且 已排序元素>待插入元素（需要后移）
          while (j >= 0 && nums[j] > current) {
              // 将nums[j]后移一位，覆盖nums[j+1]（即原current的位置）
              nums[j + 1] = nums[j];
              // j向前移动，继续比较
              j--;
          }
  
          // 3. 插入待插入元素到正确位置（j+1是最终插入位置）
          nums[j + 1] = current;
  
          // 可选：打印每一步的排序结果，便于理解
          cout << "第" << i << "轮排序后：";
          for (int num : nums) cout << num << " ";
          cout << endl;
      }
  }
  
  // 测试函数
  int main() {
      vector<int> nums = {5, 2, 9, 1, 5, 6};
      cout << "原始数组：";
      for (int num : nums) cout << num << " ";
      cout << endl;
  
      insertionSort(nums);
  
      cout << "最终排序结果：";
      for (int num : nums) cout << num << " ";
      cout << endl;
  
      return 0;
  }

• 最好情况：$O(n)$，只需遍历一次，无需移动元素

• 最坏情况：$O(n^2)$，每个元素都要移动到最前面

• 空间复杂度为 $O(1)$，原地排序，仅使用常数级额外空间

• 稳定排序：当待插入元素等于已排序区的元素时，会插入到其后方，不会改变相等元素的相对顺序

• 折半插入排序：在找插入位置时，用二分查找替代顺序遍历，减少比较次数（但移动次数不变，时间复杂度仍为 $O(n^2)$）

归并排序

• 归并排序分为两个核心阶段：分（Divide） 和治（Conquer）

• 阶段 1：分（拆分）

  • 将数组从中间拆分为左右两个子数组；
  • 递归拆分左右子数组，直到每个子数组的长度为 1（长度为 1 的数组天然有序）

• 阶段 2：治（合并）

  • 从最小的有序子数组开始，两两合并为一个更大的有序数组；
  • 逐层向上合并，最终得到完整的有序数组

• 代码实现

  #include <iostream>
  #include <vector>
  using namespace std;
  
  /**
   * 合并两个有序子数组
   * @param nums 原数组
   * @param left 左子数组起始索引
   * @param mid  中间索引（左子数组末尾=mid，右子数组起始=mid+1）
   * @param right 右子数组末尾索引
   */
  void merge(vector<int>& nums, int left, int mid, int right) {
      // 1. 创建临时数组，存储合并后的结果（长度=右-左+1）
      vector<int> temp(right - left + 1);
      // i：左子数组的指针（起始=left）
      // j：右子数组的指针（起始=mid+1）
      // k：临时数组的指针（起始=0）
      int i = left, j = mid + 1, k = 0;
  
      // 2. 合并两个有序子数组到临时数组
      while (i <= mid && j <= right) {
          // 升序规则：取较小的元素放入临时数组
          if (nums[i] <= nums[j]) {
              temp[k++] = nums[i++];
          } else {
              temp[k++] = nums[j++];
          }
      }
  
      // 3. 处理左子数组的剩余元素（如果有）
      while (i <= mid) {
          temp[k++] = nums[i++];
      }
  
      // 4. 处理右子数组的剩余元素（如果有）
      while (j <= right) {
          temp[k++] = nums[j++];
      }
  
      // 5. 将临时数组的结果复制回原数组的对应位置
      for (int p = 0; p < temp.size(); ++p) {
          nums[left + p] = temp[p];
      }
  }
  
  /**
   * 归并排序递归函数
   * @param nums 待排序数组
   * @param left 子数组起始索引
   * @param right 子数组末尾索引
   */
  void mergeSortRecursive(vector<int>& nums, int left, int right) {
      // 递归终止条件：子数组长度<=1（无需排序）
      if (left >= right) {
          return;
      }
  
      // 1. 计算中间索引（避免溢出：left + (right-left)/2 替代 (left+right)/2）
      int mid = left + (right - left) / 2;
  
      // 2. 递归拆分左子数组 [left, mid]
      mergeSortRecursive(nums, left, mid);
      // 3. 递归拆分右子数组 [mid+1, right]
      mergeSortRecursive(nums, mid + 1, right);
  
      // 4. 合并两个有序子数组
      merge(nums, left, mid, right);
  }
  
  /**
   * 归并排序对外封装（简化调用）
   * @param nums 待排序数组
   */
  void mergeSort(vector<int>& nums) {
      if (nums.empty()) return;
      mergeSortRecursive(nums, 0, nums.size() - 1);
  }
  
  // 测试函数
  int main() {
      vector<int> nums = {5, 2, 9, 1, 5, 6};
      cout << "原始数组：";
      for (int num : nums) cout << num << " ";
      cout << endl;
  
      mergeSort(nums);
  
      cout << "最终排序结果：";
      for (int num : nums) cout << num << " ";
      cout << endl;
  
      return 0;
  }

• 最好 / 最坏 / 平均情况：$O(n\log n)$

• 空间复杂度：$O(n)$，需要临时数组存储合并结果（非原地排序）

• 递归调用栈空间：$O(\log n)$

• 稳定排序：合并时当 nums[i] <= nums[j] 时取左子数组的元素，保证相等元素的相对顺序不变

• 适合要求稳定排序的场景：比如排序对象是 “键值对”（如按成绩排序，成绩相同保持原顺序）

• 算法题中的经典应用：

  • 求逆序对（归并排序的核心变种题，合并时统计逆序对数量）
  • 外部排序（数据量超过内存时，分块排序后合并）

选择排序

• 将数组分为 “已排序区” 和 “未排序区”：

  1. 遍历未排序区，找到其中的最小值（升序）；
  2. 将最小值与未排序区的第一个元素交换位置，此时该元素加入 “已排序区”；
  3. 重复步骤 1-2，直到未排序区为空

• 代码实现

  #include <iostream>
  #include <vector>
  using namespace std;
  
  void selectionSort(vector<int>& nums) {
      int n = nums.size();
      if (n <= 1) return;
  
      // 外层循环：控制已排序区的末尾（i是未排序区的第一个元素索引）
      for (int i = 0; i < n - 1; ++i) {
          // 1. 找未排序区 [i, n-1] 的最小值索引
          int minIdx = i; // 初始假设第一个元素是最小值
          for (int j = i + 1; j < n; ++j) {
              if (nums[j] < nums[minIdx]) {
                  minIdx = j; // 更新最小值索引
              }
          }
  
          // 2. 交换最小值和未排序区第一个元素
          if (minIdx != i) { // 避免自我交换
              swap(nums[i], nums[minIdx]);
          }
  
          // 可选：打印每轮结果
          cout << "第" << i+1 << "轮：";
          for (int num : nums) cout << num << " ";
          cout << endl;
      }
  }
  
  int main() {
      vector<int> nums = {5,2,9,1,5,6};
      selectionSort(nums);
      return 0;
  }

• 时间复杂度：最好 / 最坏 / 平均都是 $O(n^2)$（无论数组是否有序，都要遍历找最值）

• 空间复杂度：$O(1)$（原地排序）；

• 不稳定：交换会破坏相等元素的相对顺序，比如 [2, 3, 2] 排序时，第一个 2 会和第三个 2 交换）

• 仅适合小规模数据

堆排序

• 堆是完全二叉树，分为大顶堆（父节点≥子节点）和小顶堆（父节点≤子节点）

• 堆排序（升序）步骤：

  • 建堆：将原数组构建为大顶堆（堆顶是最大值）；
  • 排序：
    • 交换堆顶元素和堆的最后一个元素（最大值 “沉” 到数组末尾，加入已排序区）；
    • 缩小堆的范围（排除已排序的末尾元素），对新堆顶执行 “堆化”（恢复大顶堆结构）；
    • 重复上述步骤，直到堆的大小为 1

• 代码实现

  #include <iostream>
  #include <vector>
  using namespace std;
  
  /**
   * 堆化函数（维护大顶堆结构）
   * @param nums 待堆化的数组
   * @param n 堆的总大小
   * @param i 要堆化的节点索引
   */
  void heapify(vector<int>& nums, int n, int i) {
      int largest = i; // 初始化最大值为当前节点
      int left = 2 * i + 1; // 左子节点索引
      int right = 2 * i + 2; // 右子节点索引
  
      // 如果左子节点比当前节点大，更新最大值索引
      if (left < n && nums[left] > nums[largest]) {
          largest = left;
      }
      // 如果右子节点比最大值大，更新最大值索引
      if (right < n && nums[right] > nums[largest]) {
          largest = right;
      }
  
      // 如果最大值不是当前节点，交换并递归堆化受影响的子树
      if (largest != i) {
          swap(nums[i], nums[largest]);
          heapify(nums, n, largest);
      }
  }
  
  void heapSort(vector<int>& nums) {
      int n = nums.size();
      if (n <= 1) return;
  
      // 1. 构建大顶堆（从最后一个非叶子节点开始堆化）
      // 最后一个非叶子节点索引：n/2 - 1
      for (int i = n / 2 - 1; i >= 0; --i) {
          heapify(nums, n, i);
      }
  
      // 2. 逐个取出堆顶元素（最大值），放到数组末尾
      for (int i = n - 1; i > 0; --i) {
          swap(nums[0], nums[i]); // 交换堆顶和当前堆的最后一个元素
          heapify(nums, i, 0); // 堆化剩余的i个元素（缩小堆范围）
      }
  }
  
  int main() {
      vector<int> nums = {5,2,9,1,5,6};
      heapSort(nums);
      for (int num : nums) cout << num << " "; // 输出：1 2 5 5 6 9
      return 0;
  }

• 时间复杂度：建堆 $O(n)$，排序 $O(n\log n)$，整体 $O(n\log n)$（最好 / 最坏 / 平均一致）

• 空间复杂度：$O(1)$（原地排序，递归堆化的栈空间可忽略）

• 稳定性：不稳定（堆化交换会破坏相等元素的相对顺序）

• 适用场景：

  • 算法题中 “TopK 问题”（找前 k 大 / 小元素）的最优解（无需全排序）
  • 大规模数据排序（效率接近快排，且无快排的最坏情况）

希尔排序

• 希尔排序是插入排序的优化版，又称 “缩小增量排序”，属于比较类排序

• 核心是 “分组插入排序”，通过增量（步长）将数组分组，对每组执行插入排序，逐步缩小增量直到为 1（此时退化为普通插入排序，但数组已近乎有序）：

  • 选择一个增量序列（如 $n/2,n/4,\cdots,1$）；
  • 按当前增量将数组分为若干组（索引差为增量的元素为一组）；
  • 对每组执行插入排序；
  • 缩小增量，重复步骤 2-3，直到增量为 1

• 代码实现

  #include <iostream>
  #include <vector>
  using namespace std;
  
  void shellSort(vector<int>& nums) {
      int n = nums.size();
      if (n <= 1) return;
  
      // 1. 初始化增量为数组长度的一半，逐步缩小增量
      for (int gap = n / 2; gap > 0; gap /= 2) {
          // 2. 对每组执行插入排序（从gap开始遍历，每组的第一个元素是nums[0], nums[gap], nums[2gap]...）
          for (int i = gap; i < n; ++i) {
              int current = nums[i]; // 待插入元素
              int j = i;
              // 向前遍历同组元素，大于current则后移
              while (j >= gap && nums[j - gap] > current) {
                  nums[j] = nums[j - gap];
                  j -= gap;
              }
              nums[j] = current; // 插入到正确位置
          }
      }
  }
  
  int main() {
      vector<int> nums = {5,2,9,1,5,6};
      shellSort(nums);
      for (int num : nums) cout << num << " "; // 输出：1 2 5 5 6 9
      return 0;
  }

• 时间复杂度：依赖增量序列，最优 $O(n\log n)$，最坏 $O(n^2)$，平均 $O(n^{1.3})$

• 空间复杂度：$O(1)$（原地排序）

• 稳定性：不稳定（分组插入会破坏相等元素的相对顺序）

• 适用场景：中等规模数据排序，效率高于插入 / 冒泡 / 选择排序，实现简单

计数排序

• 计数排序是非比较类排序（不通过比较元素大小排序），核心是 “统计频率、还原数组”，适用于数值范围有限的整数排序

  • 确定范围：找到数组中的最大值和最小值，确定计数数组的长度；
  • 统计频率：创建计数数组，统计原数组中每个元素出现的次数；
  • 还原有序数组：遍历计数数组，按频率将元素填充回原数组

• 代码实现

  #include <iostream>
  #include <vector>
  #include <climits> // 用于INT_MIN/INT_MAX
  using namespace std;
  
  void countingSort(vector<int>& nums) {
      int n = nums.size();
      if (n <= 1) return;
  
      // 1. 找数组的最大值和最小值，确定计数范围
      int minVal = INT_MAX, maxVal = INT_MIN;
      for (int num : nums) {
          minVal = min(minVal, num);
          maxVal = max(maxVal, num);
      }
  
      // 2. 创建计数数组，长度=maxVal - minVal + 1，初始化为0
      vector<int> count(maxVal - minVal + 1, 0);
      // 统计每个元素的出现次数
      for (int num : nums) {
          count[num - minVal]++; // 偏移minVal，避免负数索引
      }
  
      // 3. 还原有序数组
      int idx = 0; // 原数组的填充索引
      for (int i = 0; i < count.size(); ++i) {
          while (count[i] > 0) {
              nums[idx++] = i + minVal; // 还原真实值
              count[i]--;
          }
      }
  }
  
  int main() {
      vector<int> nums = {5,2,9,1,5,6};
      countingSort(nums);
      for (int num : nums) cout << num << " "; // 输出：1 2 5 5 6 9
      return 0;
  }

• 时间复杂度：$O(n+k)$（n 是数组长度，k 是数值范围），线性时间

• 空间复杂度：$O(k)$（计数数组的空间）

• 稳定性：可实现稳定排序（优化计数数组为前缀和形式）

• 适用场景：

  • 数值范围小的整数排序（如成绩排序、年龄排序）
  • 算法题中 “基数排序” 的子步骤；
  • 限制：仅支持整数，且数值范围不能过大（否则计数数组空间爆炸）

基数排序

• 基数排序是非比较类排序，核心是 “按位排序”（从低位到高位 / 高位到低位），基于计数排序 / 桶排序实现

• 算法原理（以十进制、低位优先为例）

  • 确定最大位数：找到数组中的最大值，确定需要排序的位数（如 999 是 3 位）
  • 按位排序：从最低位（个位）到最高位，对每一位执行计数排序（保证稳定性）
  • 每一轮排序后，数组按当前位有序，最终整体有序

• 代码实现

  #include <iostream>
  #include <vector>
  #include <climits>
  using namespace std;
  
  // 获取数字的第d位（个位d=1，十位d=10，百位d=100...）
  int getDigit(int num, int d) {
      return (num / d) % 10;
  }
  
  void radixSort(vector<int>& nums) {
      int n = nums.size();
      if (n <= 1) return;
  
      // 1. 找最大值，确定最大位数
      int maxVal = INT_MIN;
      for (int num : nums) {
          if (num < 0) { // 简化处理：假设数组无负数（有负数可偏移）
              cerr << "暂不支持负数排序" << endl;
              return;
          }
          maxVal = max(maxVal, num);
      }
  
      // 2. 按位排序（d=1:个位，d=10:十位，d=100:百位...）
      for (int d = 1; maxVal / d > 0; d *= 10) {
          // 计数数组：0-9共10个数字
          vector<int> count(10, 0);
          vector<int> temp(n); // 临时数组存储当前位排序结果
  
          // 统计当前位的数字频率
          for (int num : nums) {
              int digit = getDigit(num, d);
              count[digit]++;
          }
  
          // 优化计数数组为前缀和（实现稳定排序）
          for (int i = 1; i < 10; ++i) {
              count[i] += count[i - 1];
          }
  
          // 从后往前遍历，保证稳定性
          for (int i = n - 1; i >= 0; --i) {
              int digit = getDigit(nums[i], d);
              temp[--count[digit]] = nums[i];
          }
  
          // 复制回原数组
          nums = temp;
      }
  }
  
  int main() {
      vector<int> nums = {53, 3, 542, 748, 14, 214};
      radixSort(nums);
      for (int num : nums) cout << num << " "; // 输出：3 14 53 214 542 748
      return 0;
  }

• 时间复杂度：$O(d∗(n+k))$（d 是最大位数，k 是基数，十进制 k=10），接近线性

• 空间复杂度：$O(n+k)$（临时数组 + 计数数组）

• 稳定性：稳定（关键：从后往前遍历填充临时数组）

• 适用场景：

  • 整数 / 字符串排序（如手机号、身份证号）
  • 数值范围大但位数少的场景（如 1-100000 的整数，位数仅 6 位）
  • 限制：需要按位拆分，不适合浮点数 / 自定义对象排序

排序算法对比

• 两大类型

  • 比较类排序（冒泡 / 快排 / 插入 / 归并 / 选择 / 堆 / 希尔）：通用但时间复杂度最低为 $O(n\log n)$
  • 非比较类排序（计数 / 基数）：线性时间，但有适用范围限制（如仅整数、数值范围小）

• 算法题中优先选择：

  • 通用场景：快排 / 归并 / 堆排
  • 数值范围小：计数排序
  • TopK 问题：堆排序（最优）
  • 近乎有序数据：插入排序 / 希尔排序

• 表格对比

  排序算法	核心思想	时间复杂度（最好）	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	关键适用场景	核心特点/注意事项
  冒泡排序	两两交换，最值冒泡到末尾	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	小规模数据、原理理解	可提前终止（无交换时），实际效率低
  选择排序	找最值，交换到已排序区末尾	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	小规模数据、原理理解	交换次数少，比较次数多，效率低于插入排序
  插入排序	插牌式，逐个插入已排序区	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	小规模/近乎有序数据、链表排序	实际效率高于冒泡/选择，STL sort小数组优化
  希尔排序	分组插入排序，缩小增量	$O(n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	中等规模数据	插入排序的优化版，效率提升显著
  快速排序	分治，基准分区	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	通用场景、大规模数据	STL sort底层核心，随机基准避免最坏情况
  归并排序	分治，先拆后合	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	稳定排序、逆序对统计、外部排序	时间复杂度稳定，需额外空间
  堆排序	大顶堆，堆顶交换到末尾	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	TopK问题、大规模数据	无最坏情况，适合内存受限场景
  计数排序	统计频率，还原数组	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	稳定	数值范围小的整数排序（如成绩）	非比较排序，仅支持整数，k为数值范围
  基数排序	按位排序，基于计数排序	$O(d*(n + k))$	$O(d*(n + k))$	$O(d*(n + k))$	$O(n + k)$	稳定	位数少的整数/字符串（如手机号）	非比较排序，d为最大位数，k为基数（10）

数组基本应用

数组的扩容

• 普通数组长度固定，扩容 / 缩容需要手动复制元素（O (n) 时间）

• 核心思路：预分配超额空间（capacity），扩容时按倍数（比如 2 倍）增长，减少扩容次数

• 关键操作：

  • 插入：尾部插入 O (1)（均摊），中间插入仍 O (n)（但减少了频繁扩容的开销）；
  • 扩容：当 size == capacity 时，分配 2 倍新空间，复制旧元素，释放旧空间

• 代码实现

  template <typename T>
  class DynamicArray {
  private:
      T* data;
      int size;       // 实际元素数
      int capacity;   // 总容量
  
      // 扩容：2 倍增长
      void resize() {
          capacity = capacity == 0 ? 4 : capacity * 2;
          T* new_data = new T[capacity];
          for (int i = 0; i < size; i++) {
              new_data[i] = data[i];
          }
          delete[] data;
          data = new_data;
      }
  
  public:
      DynamicArray() : size(0), capacity(0), data(nullptr) {}
  
      // 尾部添加（均摊 O(1)）
      void push_back(const T& val) {
          if (size == capacity) resize();
          data[size++] = val;
      }
  
      // 随机访问（O(1)）
      T& operator[](int idx) {
          if (idx < 0 || idx >= size) throw out_of_range("Index out of bounds");
          return data[idx];
      }
  };

移除数组元素

• 给定一个数组和指定数字，原地删除数组中所有指定数字，并返回移除后数组的新长度；要求不使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组

• 暴力解法

  • 两层 for 循环，外循环遍历数组元素，内循环更新数组

  • 示例代码

    class Solution {
    public:
        int removeElement(vector<int>& nums, int val) {
            int size = nums.size();
            for (int i = 0; i < size; i++) {
                if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                    for (int j = i + 1; j < size; j++) {
                        nums[j - 1] = nums[j];
                    }
                    i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                    size--; // 此时数组的大小-1
                }
            }
            return size;
    
        }
    };

  • 上述实现的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$​

• 双指针法（快慢指针法）

  • 通过一个快指针，一个慢指针，在一个 for 循环下完成

  • 快指针：寻找新的数组元素，即不包含待删除数字的新数组

  • 满指针：指向更新新数组下标的位置，每次填入了非待删除数字之后自增

  • 示例代码

    class Solution {
    public:
        int removeElement(vector<int>& nums, int val) {
            int slowIndex = 0;
            for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
                if (val != nums[fastIndex]) {
                    nums[slowIndex++] = nums[fastIndex];
                }
            }
            return slowIndex;
        }
    };

  • 上述实现的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$

• 相关题目

  • 27. 移除元素
  • 26.删除排序数组中的重复项
  • 283.移动零
  • 844.比较含退格的字符串
  • 977.有序数组的平方

对有序数组的平方排序

• 给定一个有序数组，对其每一位平方，并保证输出仍旧有序

• 暴力排序

  • 先求平方，再排序

  • 示例代码

    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& A) {
            for (int i = 0; i < A.size(); i++) {
                A[i] *= A[i];
            }
            sort(A.begin(), A.end()); // 快速排序
            return A;
        }
    };

  • 上述实现的时间复杂度为 $O(n + n\log n)$，空间复杂度为 $O(1)$

• 双指针法

  • 核心观察：数组平方的最大值始终在数组的两端出现，因此可以在数组的两端放置两个指针，哪个大就哪个就放入结果数组中，并移动该指针

  • 示例代码

    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& A) {
            int k = A.size() - 1;
            vector<int> result(A.size(), 0);
            for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
                if (A[i] * A[i] < A[j] * A[j])  {
                    result[k--] = A[j] * A[j];
                    j--;
                }
                else {
                    result[k--] = A[i] * A[i];
                    i++;
                }
            }
            return result;
        }
    };

  • 上述实现的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$​

  • 特判情况优化

    • 如果首元素非负，那么所有元素都非负，此时直接按顺序平方即可
    • 如果最后一个元素非正，那么所有元素都非正，此时直接按顺序平方并倒序即可
    • 头尾平方的大小比较直接将头尾相加与 0 相比较即可，如果大于 0 说明应该移动尾指针，否则移动头指针

• 相关题目

  • 977. 有序数组的平方

长度最小子数组

• 给定一个正整数数组和正整数，找出满足其和大于等于该整数的长度最小的连续子数组

• 暴力解法

  • 外层遍历数组的每个元素，内层遍历以该元素为起始的所有子数组，寻找所有符合条件的子数组

  • 示例代码

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int result = INT32_MAX; // 最终的结果
            int sum = 0; // 子序列的数值之和
            int subLength = 0; // 子序列的长度
            for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
                sum = 0;
                for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                    sum += nums[j];
                    if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                        subLength = j - i + 1; // 取子序列的长度
                        result = result < subLength ? result : subLength;
                        break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                    }
                }
            }
            // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
            return result == INT32_MAX ? 0 : result;
        }
    };

  • 上述实现的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$

• 滑动窗口法

  • 滑动窗口，即不断调节子序列的起始位置和终止位置

  • 以两个指针表示滑动窗口的起始和终止位置，终止指针不断右移，当窗口符合条件时，记录子序列长度，并向右移动起始指针直至窗口不再符合条件，继续重复刚刚的过程，直到最后找到符合条件的最短的子数组

  • 事实上，滑动窗口也可以看作是双指针法的一种应用

  • 这种实现方法需要关注三点：窗口内是什么？如何移动起始位置？如何移动结束位置？

  • 在本题中

    • 窗口即满足其和大于等于 s 的长度最小的连续子数组
    • 窗口的起始位置如何移动：如果当前窗口的值大于等于 s，窗口就向右进行移动，缩小窗口
    • 窗口的终止位置如何移动：即不断地遍历数组，for 循环中的索引

  • 具体实现

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int result = INT32_MAX;
            int sum = 0; // 滑动窗口数值之和
            int i = 0; // 滑动窗口起始位置
            int subLength = 0; // 滑动窗口的长度
            for (int j = 0; j < nums.size(); j++) {
                sum += nums[j];
                // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
                // 因为可能 nums[j] 是一个很大的数字，此时仅仅向右移动一次 i，可能还不是最短的子数组
                while (sum >= s) {
                    subLength = (j - i + 1); // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
                }
            }
            // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
            return result == INT32_MAX ? 0 : result;
        }
    };

  • 上述实现的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$​

• 时间复杂度的计算，主要看每一个元素被操作的次数，而在滑动窗口法中，每个元素在滑动窗口进来操作一次，出去操作一次，即被操作两次，也即 $O(2n)$

• 相关题目

  • 209. 长度最小的子数组
  • 904.水果成篮
  • 76.最小覆盖子串

螺旋矩阵

• 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵

• 模拟方法

  • 模拟顺时针画矩阵的过程：

    • 填充上行从左到右
    • 填充右列从上到下
    • 填充下行从右到左
    • 填充左列从下到上

  • 类似二分法，需要维持遍历区间的循环不变量原则，比如保持都是左闭右开，模拟转一圈过程中的四个方向的填充过程

  • 转的圈数就是 n/2，对于 n 为奇数，需要最后填充中心位置的元素

  • 示例代码

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
            int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
            int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
            int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
            int count = 1; // 用来给矩阵中每一个空格赋值
            int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
            int i,j;
            while (loop --) {
                i = startx;
                j = starty;
    
                // 下面开始的四个for就是模拟转了一圈
                // 模拟填充上行从左到右(左闭右开)
                for (j; j < n - offset; j++) {
                    res[i][j] = count++;
                }
                // 模拟填充右列从上到下(左闭右开)
                for (i; i < n - offset; i++) {
                    res[i][j] = count++;
                }
                // 模拟填充下行从右到左(左闭右开)
                for (; j > starty; j--) {
                    res[i][j] = count++;
                }
                // 模拟填充左列从下到上(左闭右开)
                for (; i > startx; i--) {
                    res[i][j] = count++;
                }
    
                // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
                startx++;
                starty++;
    
                // offset 控制每一圈里每一条边遍历的长度
                offset += 1;
            }
    
            // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
            if (n % 2) {
                res[mid][mid] = count;
            }
            return res;
        }
    };

  • 上述实现的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$

• 第二种模拟方法

  • 第一种方法围绕圈数而确定循环次数，每一圈定义四个方向的循环过程

  • 而更方便的方法是，以数字最大大小 $n^2$ 为循环条件，示例代码如下

    class Solution {
        public int[][] generateMatrix(int n) {
            int i = 0, j = 0, m = 0;
            int[][] ints = new int[n][n];
            while (m < n * n) {
                for (; j < n - i - 1; j++)            ints[i][j] = ++m;
                for (; i < j; i++)                    ints[i][j] = ++m;
                for (; j > n - i - 1; j--)            ints[i][j] = ++m;
                for (; i > j + 1 || m == n*n-1; i--)  ints[i][j] = ++m;
            }
            return ints;
        }
    }

• 第三种模拟方法

  • 上述方法中，每次循环依旧定义了四个方向的循环过程，对每个方向的边界条件进行判定

  • 而可以在每次达到边界条件后，就调整方向，示例代码如下

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> res(n, vector<int>(n, 0));
            int dx = 0, dy = 1;
            int x = 0, y = 0;
            for (int i = 1; i <= n * n; ++i) {
                res[x][y] = i;
                if (res[(x + dx) % n][(y + dy) % n] != 0) {
                    int tmp = dy;
                    dy = -dx;
                    dx = tmp;
                }
                x += dx;
                y += dy;
            }
            return res;
        }
    };

  • 进一步的，可以定义一个方向数组，示例代码如下

    class Solution {
        public int[][] generateMatrix(int n) {
            // 定义四个方向，按顺时针方向
            int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int directionIndex = 0;
            // 初始化矩阵和起始位置
            int[][] matrix = new int[n][n];
            int y = 0;
            int x = 0;
            int step = 1;
            while (step <= n * n) {
                matrix[y][x] = step++;
                if (step > n * n) {
                    break;
                }
                // 先尝试往之前的方向继续走
                int[] direction = directions[directionIndex];
                int nextY = y + direction[0];
                int nextX = x + direction[1];
                // 不能走（超过边界或走过）再试其它方向
                while (nextX < 0 || n <= nextX || nextY < 0 || n <= nextY || matrix[nextY][nextX] != 0) {
                    directionIndex = (directionIndex + 1) % directions.length;
                    direction = directions[directionIndex];
                    nextY = y + direction[0];
                    nextX = x + direction[1];
                }
                y = nextY;
                x = nextX;
            }
            return matrix;
        }
    }

• 相关题目

  • 54. 螺旋矩阵：非方阵
  • 59. 螺旋矩阵 II：方阵
  • 885. 螺旋矩阵 III：任意位置开始，且可以越界
  • 2326. 螺旋矩阵 IV：链表+非方阵
  • LCR 146. 螺旋遍历二维数组

二分查找

二分查找模板

• 二分查找的前提：数组必须有序，且没有重复元素

• 二分查找的关键：对边界条件的处理

  • 最重要的是先弄清楚二分查找的区间定义
  • 在二分查找的过程中，需要保持区间的定义为不变量，在 while 查找中每一次对边界的处理都要坚持根据区间的定义来操作——循环不变量原则

• 二分法的区间定义一般为两种，左闭右闭即 [left, right]，或者左闭右开即 [left, right)

• 在左闭右闭的类型中

  • while(left <= right)：因为右边是闭区间，left==right 是有意义的

  • if(nums[middle] > target)) right = middle - 1：因为要保持左闭右闭的不变量，而 nums[middle] 一定不是 target，因此接下来要查找的区间的下标位置就是 middle - 1

  • 代码示例

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
            while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
                int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
                if (nums[middle] > target) {
                    right = middle - 1; // target 在左区间，所以[left, middle - 1]
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间，所以[middle + 1, right]
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值，直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };

  • 上述实现的时间复杂度为 $O(log n)$，空间复杂度为 $O(1)$

• 在左闭右开的类型中

  • while(left < right)：因为右边是开区间，left==right 是无法取到的

  • if(nums[middle] > target)) right = middle：因为要保持左闭右开的不变量，而 nums[middle] 不等于 target，因此接下来要查找的区间的下标位置就是 middle

  • 代码示例

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
            while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
                int middle = left + ((right - left) >> 1);
                if (nums[middle] > target) {
                    right = middle; // target 在左区间，在[left, middle)中
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间，在[middle + 1, right)中
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值，直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };

  • 上述实现的时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$

• 找最后一个或第一个目标值的索引

  // 找第一个等于target的索引
  int binarySearchFirst(const vector<int>& nums, int target) {
      int left = 0, right = nums.size() - 1;
      int res = -1; // 初始化为未找到
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
              res = mid; // 记录找到的索引
              right = mid - 1; // 继续找左边的相同元素
          } else if (nums[mid] > target) {
              right = mid - 1;
          } else {
              left = mid + 1;
          }
      }
      return res;
  }
  
  // 找最后一个等于target的索引
  int binarySearchLast(const vector<int>& nums, int target) {
      int left = 0, right = nums.size() - 1;
      int res = -1;
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
              res = mid; // 记录找到的索引
              left = mid + 1; // 继续找右边的相同元素
          } else if (nums[mid] > target) {
              right = mid - 1;
          } else {
              left = mid + 1;
          }
      }
      return res;
  }

• 相关题目

  • 704. 二分查找
  • 35.搜索插入位置
  • 34.在排序数组中查找元素的第一个和最后一个位置
  • 69.x 的平方根
  • 367.有效的完全平方数

二分查找变形

• 设 nums 为递增（非递减）数组，长为 $n$

• 常用转化

  需求	写法	如果不存在
  $\ge x$ 的第一个元素的下标	lowerBound(nums, x)	结果为 $n$
  $> x$ 的第一个元素的下标	lowerBound(nums, x + 1)	结果为 $n$
  $< x$ 的最后一个元素的下标	lowerBound(nums, x) - 1	结果为 $-1$
  $\le x$ 的最后一个元素的下标	lowerBound(nums, x + 1) - 1	结果为 $-1$

• 求个数

  需求	写法
  $< x$ 的元素个数	lowerBound(nums, x)
  $\le x$ 的元素个数	lowerBound(nums, x + 1)
  $\ge x$ 的元素个数	$n - \text{lowerBound}(nums, x)$
  $> x$ 的元素个数	$n - \text{lowerBound}(nums, x + 1)$

• 注意：$< x$ 和 $\ge x$ 互为补集，元素个数之和为 $n$；$\le x$ 和 $> x$​ 同理

• 实现 lowerBound 函数

  // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
  // 如果数组为空，或者所有数都 < target，则返回 nums.size()
  // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
  int lower_bound(vector<int>& nums, int target) {
      int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
      while (left <= right) { // 区间不为空
          // 循环不变量：
          // nums[left-1] < target
          // nums[right+1] >= target
          int mid = left + (right - left) / 2;
          if (nums[mid] >= target) {
              right = mid - 1; // 范围缩小到 [left, mid-1]
          } else {
              left = mid + 1; // 范围缩小到 [mid+1, right]
          }
      }
      // 循环结束后 left = right+1
      // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
      // 所以 left 就是第一个 >= target 的元素下标
      return left;
  }

• 为何二分查找中找到 target 不立即返回？

  • 在二分查找过程中，若找到等于 target 的元素就立即返回下标，这种实现方式的适用场景会非常有限，核心原因如下：

  • 无法保证返回首个匹配元素的下标：当数组中存在多个等于 target 的元素时（如有序数组 [1,1,3,3,3,3,5]），中途找到 target 就返回，得到的下标可能是任意一个匹配元素的位置，而非第一个等于 target 的元素下标

  • 首个匹配下标具备更强的通用性：返回第一个等于 target 的元素下标，能够解决更复杂的问题场景。例如，要计算上述数组中 “小于 3 的元素个数”：

    • 若通过二分找到第一个等于 3 的元素下标（即 2），则下标小于 2 的所有元素均为小于 3 的数，可直接得出个数为 2；
    • 若二分中途找到 3 就返回（可能返回下标 3、4、5 等），则无法准确计算出 “小于 3 的元素个数”，导致答案错误

  • 综上，二分查找中不急于返回匹配到的 target 下标，而是持续收缩区间直至找到首个匹配项，是为了保证逻辑的通用性，满足更多实际问题的求解需求

• 实现 upperBound 函数

  // upper_bound 返回最小的满足 nums[i] > target 的下标 i
  // 如果数组为空，或者所有数都 <= target，则返回 nums.size()
  // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
  int upper_bound(vector<int>& nums, int target) {
      int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
      while (left <= right) { // 区间不为空
          // 循环不变量：
          // nums[left-1] <= target
          // nums[right+1] > target
          int mid = left + (right - left) / 2; // 避免整数溢出，等价于 (left+right)/2
          if (nums[mid] > target) {
              right = mid - 1; // 范围缩小到 [left, mid-1]
          } else {
              left = mid + 1; // 范围缩小到 [mid+1, right]
          }
      }
      // 循环结束后 left = right+1
      // 此时 nums[left-1] <= target 而 nums[left] = nums[right+1] > target
      // 所以 left 就是第一个 > target 的元素下标
      return left;
  }

• 需求的实现

  // 1. 找到 >= x 的第一个元素的下标（等价于直接调用 lower_bound）
  int find_first_ge(vector<int>& nums, int x) {
      return lower_bound(nums, x);
  }
  
  // 2. 找到 > x 的第一个元素的下标（等价于找 >= x+1 的第一个下标）
  int find_first_gt(vector<int>& nums, int x) {
      return lower_bound(nums, x + 1);
  }
  
  // 3. 找到 < x 的最后一个元素的下标（不存在则返回 -1）
  int find_last_lt(vector<int>& nums, int x) {
      int idx = lower_bound(nums, x) - 1;
      return idx; // 若所有元素 >=x，idx 会是 -1，符合要求
  }
  
  // 4. 找到 <= x 的最后一个元素的下标（不存在则返回 -1）
  int find_last_le(vector<int>& nums, int x) {
      int idx = lower_bound(nums, x + 1) - 1;
      return idx;
  }
  
  // 5. 统计 < x 的元素个数（等价于 >=x 的第一个下标）
  int count_less(vector<int>& nums, int x) {
      return lower_bound(nums, x);
  }
  
  // 6. 统计 <= x 的元素个数（等价于 >x 的第一个下标）
  int count_le(vector<int>& nums, int x) {
      return lower_bound(nums, x + 1);
  }
  
  // 7. 统计 >= x 的元素个数
  int count_ge(vector<int>& nums, int x) {
      int n = nums.size();
      return n - lower_bound(nums, x);
  }
  
  // 8. 统计 > x 的元素个数
  int count_gt(vector<int>& nums, int x) {
      int n = nums.size();
      return n - lower_bound(nums, x + 1);
  }

在排序数组中查找元素的第一个和最后一个位置

• 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置

• 如果数组中不存在目标值 target，返回 [-1, -1]

• 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

• 代码实现

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int left = 0, right = nums.size() - 1, mid = 0;
          while (left <= right) {
              mid = left + (right - left) / 2;
              if (nums[mid] < target) {
                  left = mid + 1;
              } else if (nums[mid] > target) {
                  right = mid - 1;
              } else {
                  int leftRange = mid, rightRange = mid;
                  while (leftRange > 0 && nums[leftRange - 1] == target)
                      leftRange--;
                  while (rightRange < nums.size() - 1 &&
                         nums[rightRange + 1] == target)
                      rightRange++;
                  return {leftRange, rightRange};
              }
          }
          return {-1, -1};
      }
  };

• 使用 lowerBound 函数实现

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int start = lower_bound(nums, target);
          if (start == nums.size() || nums[start] != target) {
              return {-1, -1}; // nums 中没有 target
          }
          // 如果 start 存在，那么 end 必定存在
          int end = lower_bound(nums, target + 1) - 1;
          return {start, end};
      }
  };

• 库函数实现

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int start = ranges::lower_bound(nums, target) - nums.begin();
          if (start == nums.size() || nums[start] != target) {
              return {-1, -1};
          }
          int end = ranges::lower_bound(nums, target+1) - nums.begin() - 1;
          return {start, end};
      }
  };

• 关于 end = lowerBound(nums, target + 1) - 1 的逻辑解析

  • 若要查找数组中小于等于 target 的最后一个元素的下标，无需单独编写新的二分查找逻辑，可复用已实现的 lowerBound 函数（用于查找大于等于目标值的第一个元素下标）：
    • 核心思路是先定位到该目标元素的右侧相邻元素，即大于 target 的第一个元素的下标；
    • 在数组元素均为整数的前提下，“大于 target” 等价于 “大于等于 target + 1”，因此可直接调用 lowerBound(nums, target + 1) 得到该右侧相邻元素的下标；
    • 将该下标减 1，即可得到数组中小于等于 target 的最后一个元素的下标，即 end = lowerBound(nums, target + 1) - 1。
  • 关于 lowerBound(nums, target + 1) 返回值不存在的情况（即无大于等于 target + 1 的元素）：
    • 此情况表明数组中所有元素均小于等于 target；
    • 由于数组是递增排列的，若数组中存在 target，则最后一个元素（下标为 n−1，n 为数组长度）即为 target；
    • 此时 lowerBound(nums, target + 1) 会返回数组长度 n，将其减 1 后得到 n−1，恰好是数组最后一个元素的下标，与我们需要查找的结果一致

搜索二维矩阵

• 参考题目
  • 74. 搜索二维矩阵
  • 240. 搜索二维矩阵 II

二分答案

二分答案模板

• 二分区间的本质是「待验证区间」

  • 初始二分区间 [left, right] 只是我们 “猜” 的需要验证的范围；
  • 那些不在这个区间里的数，要么是「已经确定不满足条件」（比如 <10 的数），要么是「已经确定满足条件」（比如 > 32 的数）；
  • 二分的过程只是缩小待验证范围，直到待验证范围为空，此时 left 自然指向「第一个满足条件的数」（哪怕这个数不在初始区间里）

• 二分答案的核心是利用单调性（除数越大，求和结果越小）：

  1. 确定判断条件：给定一个除数 m，计算 sum(ceil(nums[i]/m))，判断是否 ≤ threshold
  2. 二分查找框架：在一个范围内找最小的 m，满足上述条件。
  3. 边界收缩：
  • 如果当前 m 满足条件 → 尝试找更小的，收缩右边界；
  • 如果不满足 → 必须增大 m，收缩左边界
  4. 优化初始范围的上下界可以减少二分查找次数

• 二分答案的一个难点是 check 函数怎么写，这会涉及到贪心等技巧

• 代码模板

  class Solution {
  public:
      // 计算满足 check(x) == true 的最小整数 x
      int binarySearchMin(vector<int>& nums) {
          // 二分猜答案：判断 mid 是否满足题目要求
          auto check = [&](int mid) -> bool {
  
          };
  
          int left = ; // 循环不变量：check(left) 恒为 false
          int right = ; // 循环不变量：check(right) 恒为 true
          // 闭区间写法：[left, right] 不为空时继续循环
          while (left <= right) {
              int mid = left + (right - left) / 2;
              if (check(mid)) { // 说明 check(>= mid 的数) 均为 true
                  right = mid - 1; // 收缩右边界，在 [left, mid-1] 中找更小的解
              } else { // 说明 check(<= mid 的数) 均为 false
                  left = mid + 1; // 收缩左边界，在 [mid+1, right] 中找解
              }
          }
          // 循环结束后 left > right
          // 此时 check(right) == false 而 check(left) == true
          // 所以 left 就是最小的满足 check 的值
          return left;
      }
  };

求最小

使结果不超过阈值的最小除数

• 题目：1283. 使结果不超过阈值的最小除数

• 给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和

• 请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个

• 每个数除以除数后都向上取整

• 关于向上取整

  • 关于上取整的计算，当 $a$ 和 $b$ 均为正整数时，有

    $$\left\lceil\dfrac{a}{b}\right\rceil = \left\lfloor\dfrac{a+b-1}{b}\right\rfloor = \left\lfloor\dfrac{a-1}{b}\right\rfloor + 1$$

  • 证明见 上取整下取整转换公式的证明

  • 对于任意除数 $m$，有两个关键不等式（向上取整的数学性质）：

    • $\lceil \frac{x}{m} \rceil \ge \frac{x}{m}$ （向上取整结果 ≥ 原除法结果）
    • $\lceil \frac{x}{m} \rceil \le \frac{x-1}{m} + 1 = \frac{x + m - 1}{m}$ （向上取整的等价公式）

• 满足二分答案性质

  • 假设除数为 $m$，根据题意，每个数除以 $m$ 再上取整，元素和为

    $$\sum_{i=0}^{n-1} \left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil$$

  • 由于 $m$ 越大，上式越小，有单调性，可以二分答案

  • 最小的满足 $\sum\limits_{i=0}^{n-1} \left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil \le \textit{threshold}$ 的 $m$ 就是答案

• 边界条件

  • 闭区间左端点初始值：$1$
  • 闭区间右端点初始值：$\max(\textit{nums})-1$，此时 $\sum\limits_{i=0}^{n-1} \left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil =n\le \textit{threshold}$ 一定成立
  • 注意题目数据范围保证 $n\le \textit{threshold}$

• 左边界条件的优化

  • 利用向上取整的下界性质：

    $$\sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil \ge \sum_{i=0}^{n-1} \frac{nums[i]}{m} = \frac{s}{m}$$

  • 因为目标是让求和结果 ≤ threshold，所以：

    $$\frac{s}{m} \le \sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil \le threshold$$

  • 变形得：$m \ge \frac{s}{threshold}$

  • 但这是理论下界，结合题目中“每个数向上取整”的特性，可以进一步收紧下界：

  • 已知 $\lceil \frac{x}{m} \rceil \ge 1$（因为 $x$ 是正整数，$m$ 是正整数），所以 $\sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil \ge n$

  • 如果假设求和结果的“宽松上限”是 $threshold + n$（用于缩小左边界范围），则：

    $$\frac{s}{m} \le threshold + n$$

  • 变形得

    $$m \ge \frac{s}{threshold + n}$$

  • 由于 $m$ 是正整数，取整后就是：$m \ge \lfloor \frac{s-1}{threshold + n} \rfloor$

  • 这就是优化后的 left，用 $s-1$ 是为了处理整除的情况，比如 $s=10, threshold+n=5$ 时，$(10-1)//5=1$，而 $10//5=2$，更贴合整数取整逻辑

• 右边界条件的优化

  • 利用向上取整的上界公式 $\lceil \frac{x}{m} \rceil \le \frac{x + m - 1}{m}$，对数组求和：

    $$\sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil \le \sum_{i=0}^{n-1} \frac{nums[i] + m - 1}{m} = \frac{s + n(m-1)}{m} = \frac{s - n}{m} + n$$

  • 要让求和结果 ≤ threshold，因此：

    $$\frac{s - n}{m} + n \le threshold$$

  • 变形：

    $$\frac{s - n}{m} \le threshold - n\\ m \ge \frac{s - n}{threshold - n}$$

  • 但这不是上界，换个思路：要找“一定满足条件”的最大 $m$ 作为上界

  • 已知当 $m = max(nums)$ 时，$\sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil = n \le threshold$（题目保证 $n \le threshold$）

  • 但可以更精确：回到向上取整的核心，若 $m$ 满足 $\sum_{i=0}^{n-1} \lceil \frac{nums[i]}{m} \rceil \le threshold$，则：

    $$\lceil \frac{max(nums)}{m} \rceil \le threshold$$

  • 因为单个元素的向上取整结果 ≤ 总和

  • 变形得：

    $$m \ge \frac{max(nums)}{threshold}$$

  • 结合总和的上界推导，要找“足够大的 $m$ 使得求和结果一定 ≤ threshold”，取最宽松的上界：

  • 当 $m = \frac{s}{threshold} + 1$ 时，必然满足条件

  • 同样转为整数取整：$m \le \lfloor \frac{s-1}{threshold} \rfloor + 1$

  • 这就是优化后的 right，$+1$ 是为了确保上界覆盖所有可能的解

• 此时 $\sum\limits_{i=0}^{n-1} \left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil \le \textit{threshold}$ 变成

  $$\sum\limits_{i=0}^{n-1} 1+ \left\lfloor\dfrac{\textit{nums}[i] - 1}{m}\right\rfloor \le \textit{threshold}$$

• 即

  $$\sum\limits_{i=0}^{n-1} \left\lfloor\dfrac{\textit{nums}[i] - 1}{m}\right\rfloor \le \textit{threshold} - n$$

• 时间复杂度：$\mathcal{o}(n\log u)$，其中 $n$ 是 $\textit{nums}$ 的长度，$u=\max(\textit{nums})$；二分 $\mathcal{o}(\log u)$ 次，每次 $\mathcal{o}(n)$ 遍历 $\textit{nums}$

• 空间复杂度：$\mathcal{o}(1)$

• 注意「求最小」和「求最大」的二分写法上的区别

  • 「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）
  • 「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别

• 代码实现

  class Solution {
  public:
      // 题目：找到最小的除数 m，使得数组中每个数除以 m 的向上取整之和 ≤ threshold
      int smallestDivisor(vector<int>& nums, int threshold) {
          // 验证函数：判断除数 m 是否满足「所有数除以 m 的向上取整之和 ≤ threshold」
          auto check = [&](int m) -> bool {
              int sum = 0; // 存储所有数除以 m 向上取整的和
              for (int x : nums) {
                  // (x + m - 1) / m 是整数除法实现向上取整的经典写法（等价于 ceil(x/m)）
                  sum += (x + m - 1) / m;
                  if (sum > threshold) { // 提前退出：和已超过阈值，无需继续计算
                      return false;
                  }
              }
              return true; // 所有数计算完后和仍≤阈值，m 是可行解
          };
  
          // ========== 闭区间二分 ==========
          // 初始左边界设为1（除数不能为0，1是最小有效除数）
          int left = 1;
          // 初始右边界仍为数组最大值（保证 check(right) 恒为 true）
          int right = ranges::max(nums);
  
          // 闭区间循环条件：[left, right] 不为空时继续
          while (left <= right) {
              int mid = left + (right - left) / 2; // 计算中间值，避免溢出
              if (check(mid)) {
                  // mid 是可行解，尝试找更小的除数 → 收缩右边界
                  right = mid - 1;
              } else {
                  // mid 不可行，需要更大的除数 → 收缩左边界
                  left = mid + 1;
              }
          }
  
          // 循环结束后 left > right，left 是第一个满足 check 的最小除数
          return left;
      }
  };