罗罗编程学习记录
本页内容 展开查看

02.5.1.2 旋转数组与部分有序

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找

02.5.1.2-001 旋转排序数组是什么结构?

一句话结论

原升序数组在某断点旋转,拆成两段各自有序的非递减子数组,且前段元素整体大于后段;例如 [4,5,6,7,0,1,2];二分需先判断哪一半有序。

概念解释

  • 两段有序。
  • 断点两侧大小关系。
  • 全局非单调。

原理流程

  1. 找断点。
  2. 分段有序。
  3. 判定目标落在哪段。

代码 / 图示

[4,5,6,7 | 0,1,2]
断点后段小于前段

常见误区

  • 误区:旋转数组全局有序;正解:只分段有序。
  • 误区:断点位置固定;正解:断点任意。

追问

  • Q:无旋转算退化情形吗? A:算,断点在末尾。
  • Q:降序旋转? A:比较方向相应反转。

02.5.1.2-002 搜索旋转排序数组(LC 33,无重复)怎么做?

一句话结论

每次中点先判断左半还是右半有序;目标落在有序区间内则收缩该侧,否则去另一侧;O(log n);数组无重复元素。

概念解释

  • 分段有序判定。
  • 目标区间归属。
  • 折半排除。

原理流程

  1. 中点命中返回。
  2. a[l] <= a[mid] 左半有序。
  3. 判定目标在左半有序区间则收缩左,否则右。

代码 / 示例

public int search(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) return mid;
        if (a[l] <= a[mid]) { // 左半有序
            if (a[l] <= target && target < a[mid]) r = mid - 1;
            else l = mid + 1;
        } else { // 右半有序
            if (a[mid] < target && target <= a[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

常见误区

  • 误区:直接按全局有序比较;正解:先分哪半有序。
  • 误区:有序区间判定漏等号;正解:a[l]<=a[mid] 含单边有序。

追问

  • Q:为什么左半条件用 <=? A:l==mid 时左半单点也有序。
  • Q:找不到返回? A:-1。

02.5.1.2-003 含重复元素(LC 81)怎么处理?

一句话结论

当 a[l] == a[mid] 无法判断哪半有序,只能 l++ 收缩跳过重复;最坏退化 O(n),平均 O(log n);其余判定同无重复版本。

概念解释

  • 等值模糊方向。
  • 单点收缩。
  • 最坏退化。

原理流程

  1. 命中返回。
  2. 等值无法分段则 l++。
  3. 其余按有序段判定。

代码 / 示例

public boolean search(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) return true;
        if (a[l] == a[mid]) { l++; continue; }
        if (a[l] < a[mid]) {
            if (a[l] <= target && target < a[mid]) r = mid - 1;
            else l = mid + 1;
        } else {
            if (a[mid] < target && target <= a[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return false;
}

常见误区

  • 误区:有重复仍保证 O(log n);正解:最坏 O(n)。
  • 误区:等值时直接猜方向;正解:无法判断只能收缩。

追问

  • Q:最坏什么数据? A:大量首尾相等,断点无法定位。
  • Q:去重后再二分? A:题目一般不允许预处理。

02.5.1.2-004 找旋转数组最小值(LC 153,无重复)怎么做?

一句话结论

最小值是断点后段首元素;中点大于右界则断点在右半,否则在左半;收缩到区间只剩一个即最小值;O(log n)。

概念解释

  • 断点即最小值。
  • 比较中点与右界。
  • 收缩定位。

原理流程

  1. a[mid] > a[r]:最小值在右。
  2. 否则在左(含 mid)。
  3. 终止返回。

代码 / 示例

public int findMin(int[] a) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > a[r]) l = mid + 1;
        else r = mid;
    }
    return a[l];
}

常见误区

  • 误区:与左界比较定位最小值;正解:与右界比较更稳,避免无旋转歧义。
  • 误区:无旋转时仍找断点;正解:r=mid 自然收敛到首元素。

追问

  • Q:为什么不用 a[l] 比较? A:无旋转时 a[l] 最小,比较方向会矛盾。
  • Q:最小值下标? A:返回 l。

02.5.1.2-005 含重复的最小值(LC 154)怎么做?

一句话结论

a[mid] > a[r] 收缩左界;a[mid] < a[r] 收缩右界;相等时 r-- 跳过重复;最坏 O(n);最小值不变性。

概念解释

  • 等值无法定位。
  • 右界收缩。
  • 最坏退化。

原理流程

  1. 比较 mid 与 r。
  2. 大小分侧。
  3. 等值 r--。

代码 / 示例

public int findMin(int[] a) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > a[r]) l = mid + 1;
        else if (a[mid] < a[r]) r = mid;
        else r--;
    }
    return a[l];
}

常见误区

  • 误区:等值时 l++;正解:与右界比较口径下 r--。
  • 误区:重复数据仍 O(log n);正解:最坏 O(n)。

追问

  • Q:最小值可能在被跳过的位置吗? A:等值时最小值两侧都可能,r-- 不丢最小值。
  • Q:与 LC 153 区别? A:多等值分支。

02.5.1.2-006 怎么判断哪一半有序?

一句话结论

无重复时 a[l] <= a[mid] 左半有序(l==mid 单点也算),否则右半有序;有序段满足端点大小关系;再用端点判定目标归属。

概念解释

  • 端点比较。
  • 单点有序。
  • 分段归属。

原理流程

  1. 比较左界与中点。
  2. 左半有序或右半有序。
  3. 目标区间判定。

代码 / 图示

a[l] <= a[mid] → 左半有序
否则 → 右半有序

常见误区

  • 误区:a[l] < a[mid] 漏掉单点;正解:用 <=。
  • 误区:两段同时判有序;正解:旋转数组至多一段在本轮有序。

追问

  • Q:完全有序数组? A:左半恒有序,退化为普通二分。
  • Q:等值时? A:无法判断,收缩跳过。

02.5.1.2-007 目标是否在有序区间怎么判定?

一句话结论

左半有序:a[l] <= target && target < a[mid] 进左半;右半有序:a[mid] < target && target <= a[r] 进右半;端点等号按区间开闭写清。

概念解释

  • 区间端点。
  • 闭区间判定。
  • 排除另一侧。

原理流程

  1. 确定有序段。
  2. 端点夹逼 target。
  3. 命中区间收缩,否则反向。

代码 / 图示

左半:[a[l], a[mid])
右半:(a[mid], a[r]]

常见误区

  • 误区:端点等号漏写导致边界值走错侧;正解:与区间口径一致。
  • 误区:用无序段端点夹逼;正解:只在有序段内夹逼。

追问

  • Q:target 等于 mid? A:开头已命中返回。
  • Q:有序段为空? A:l==mid 单点,判定退化为等值比较。

02.5.1.2-008 旋转数组二分为什么仍能 O(log n)?

一句话结论

无重复时每轮至少有一段有序,可据端点排除一半;区间严格折半;含重复时等值轮次无法排除,最坏退化 O(n)。

概念解释

  • 半段有序保证排除。
  • 折半收敛。
  • 重复退化。

原理流程

  1. 每轮判定有序段。
  2. 排除不含目标侧。
  3. 规模减半。

代码 / 图示

无重复:O(log n)
有重复:平均 O(log n),最坏 O(n)

常见误区

  • 误区:旋转数组不能二分;正解:分段有序仍可折半。
  • 误区:有重复也报 O(log n);正解:最坏 O(n)。

追问

  • Q:O(log n) 前提? A:无重复或重复不影响分段判定。
  • Q:n 很大重复多? A:退化线性,考虑预处理。

02.5.1.2-009 数组原地轮转是什么思路?

一句话结论

把数组后 k 位移到前部:三次反转(整体反转、前 k 反转、后 n-k 反转)原地完成;O(n) 时间 O(1) 空间;与二分找断点是两类问题。

概念解释

  • 反转拼接。
  • 原地交换。
  • 非二分。

原理流程

  1. 整体反转。
  2. 前 k 反转。
  3. 后段反转。

代码 / 示例

void rotate(int[] a, int k) {
    k %= a.length;
    reverse(a, 0, a.length - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, a.length - 1);
}

常见误区

  • 误区:轮转问题用二分;正解:反转法 O(n)。
  • 误区:k 未取模;正解:k 可能大于 n。

追问

  • Q:额外数组做法? A:复制到新数组按位置回填 O(n) 空间。
  • Q:LC 189? A:本框架对应。

02.5.1.2-010 怎么求旋转了多少次(断点下标)?

一句话结论

断点即最小值下标;找最小值位置 k,前 k 个元素被转到末尾;无旋转 k=0;复用最小值二分模板。

概念解释

  • 断点 = 最小值位置。
  • 旋转次数。
  • 无旋转基准。

原理流程

  1. 二分定位最小值下标。
  2. 该下标即断点。
  3. 次数 = 下标。

代码 / 图示

[4,5,6,7,0,1,2] 最小值下标 4 → 旋转 4 位

常见误区

  • 误区:断点是最大值位置;正解:旋转后最小值为首断点。
  • 误区:无旋转断点记为 n;正解:k=0。

追问

  • Q:多次旋转等价一次? A:取模合并。
  • Q:重复元素断点唯一吗? A:最小值可能多处。

02.5.1.2-011 部分有序数组的通用二分思路是什么?

一句话结论

先识别有序区段(端点比较),在有序段内判定目标归属;无法保证全局单调时,靠分段单调性排除一侧;每轮必须能排除至少一半。

概念解释

  • 分段单调。
  • 区段判定。
  • 排除一半。

原理流程

  1. 找有序段。
  2. 端点夹逼。
  3. 排除另一侧。

代码 / 图示

有序段 → 夹逼 → 收缩

常见误区

  • 误区:部分有序直接全局比较;正解:先分段。
  • 误区:无法排除一半仍硬二分;正解:退化线性。

追问

  • Q:山峰数组? A:局部单调,比较两侧斜率。
  • Q:二维部分有序? A:见 02.5.1.4。

02.5.1.2-012 旋转数组有哪些边界用例?

一句话结论

无旋转、单元素、两元素、全部相等、断点在首尾、target 等于端点、重复首尾;检查分段判定与等值退化。

概念解释

  • 退化情形。
  • 端点等值。
  • 重复退化。

原理流程

  1. 无旋转走普通二分。
  2. 单点直接返回。
  3. 等值分支收缩。

代码 / 图示

[1,2,3] / [1] / [2,1]
全相等 / target=端点

常见误区

  • 误区:无旋转仍判断点;正解:自然退化为普通二分。
  • 误区:两元素分段误判;正解:l==mid 视为单点有序。

追问

  • Q:空数组? A:返回 -1/false。
  • Q:target 不存在? A:区间收敛后判 -1。

02.5.1.2-013 无旋转退化情形怎么处理?

一句话结论

数组完全有序时,左半恒有序,判定等价于普通二分;模板无需特判,a[l]<=a[mid] 恒成立;自然走普通收缩路径。

概念解释

  • 恒有序段。
  • 模板兼容。
  • 无需特判。

原理流程

  1. 比较左界中点。
  2. 恒左半有序。
  3. 普通夹逼收缩。

代码 / 图示

[1,2,3,4,5]:左半恒有序

常见误区

  • 误区:额外判断是否旋转;正解:模板兼容退化。
  • 误区:无旋转走右半分支;正解:端点关系决定。

追问

  • Q:降序退化? A:比较方向反转。
  • Q:怎么自测退化? A:用有序数组跑模板。

02.5.1.2-014 重复元素为什么会退化线性?

一句话结论

a[l]==a[mid] 时左右段端点相等,无法判断断点在哪侧,只能逐点收缩;大量重复时每轮排除极少,最坏 O(n)。

概念解释

  • 信息不足。
  • 单点收缩。
  • 退化线性。

原理流程

  1. 等值无法分段。
  2. l++ 或 r--。
  3. 区间仅减一。

代码 / 图示

[1,1,1,1,2,1,1] 等值轮次无法折半

常见误区

  • 误区:重复元素仍 O(log n);正解:最坏 O(n)。
  • 误区:等值时猜一侧;正解:可能漏解。

追问

  • Q:LC 81 最坏复杂度? A:O(n)。
  • Q:怎么优化重复场景? A:预处理去重(题意允许时)。

02.5.1.2-015 旋转数组二分常见错误有哪些?

一句话结论

边方向写反、有序段判定漏等号、有序段外用无序端点夹逼、等值未收缩、端点等号错位、无旋转误判断点;按分段判定 → 夹逼 → 收缩复核。

概念解释

  • 方向。
  • 判定条件。
  • 夹逼口径。

原理流程

  1. 复核哪半有序。
  2. 复核夹逼端点。
  3. 复核等值分支。

代码 / 图示

有序段判定 → 区间夹逼 → 边界更新

常见误区

  • 误区:把 a[mid] 当有序端点;正解:用段两端点。
  • 误区:target 等于端点走错侧;正解:等号归属写清。

追问

  • Q:怎么自测? A:构造断点在不同位置的样例。
  • Q:找不到元素? A:检查端点夹逼是否过严。

02.5.1.2-016 二分找断点与普通最小值查找有何区别?

一句话结论

普通有序数组最小值在端点;旋转数组最小值为断点,需比较中点与右界定位;本质都是二分单调性质,只是比较参照点不同。

概念解释

  • 有序:端点已知。
  • 旋转:断点未知。
  • 比较参照。

原理流程

  1. 有序取端点。
  2. 旋转比较 mid 与 r。
  3. 收缩到断点。

代码 / 图示

有序:a[0] 最小
旋转:mid > a[r] → 右半找

常见误区

  • 误区:旋转最小值仍取左端点;正解:左端点是前段最大附近。
  • 误区:比较参照混用;正解:固定与右界比。

追问

  • Q:峰值数组找最大值? A:对称比较。
  • Q:断点与最小值关系? A:旋转后同一位置。

02.5.1.2-017 旋转数组与二分查找基础题怎么衔接?

一句话结论

先掌握 02.5.1.1 区间不变量与上下界模板,再在分段有序场景中加“哪半有序”判定;收缩方向仍由区间口径保证;新增分支不改变二分框架。

概念解释

  • 框架复用。
  • 分段判定附加。
  • 口径不变。

原理流程

  1. 固定区间口径。
  2. 加有序段判定。
  3. 套用夹逼收缩。

代码 / 图示

基础二分 + 分段判定 = 旋转二分

常见误区

  • 误区:旋转题另起一套死循环口径;正解:复用基础模板。
  • 误区:新增分支破坏不变量;正解:候选侧仍保留。

追问

  • Q:学旋转题前先掌握什么? A:lower_bound 与边界更新。
  • Q:分段判定属于哪一步? A:比较后的排除侧选择。

02.5.1.2-018 旋转数组复杂度怎么汇报?

一句话结论

无重复 O(log n) 时间 O(1) 空间;含重复平均 O(log n)、最坏 O(n);找最小值同口径;空间均 O(1) 迭代。

概念解释

  • 折半对数。
  • 重复退化。
  • 辅助常数。

原理流程

  1. 标注是否有重复。
  2. 每轮排除规模。
  3. 分列时间空间。

代码 / 图示

无重复:O(log n) / O(1)
有重复:最坏 O(n) / O(1)

常见误区

  • 误区:旋转数组统一 O(log n);正解:重复最坏 O(n)。
  • 误区:递归实现不计栈;正解:迭代 O(1)。

追问

  • Q:找最小值与查找 target 同复杂度吗? A:同口径。
  • Q:n 规模下 O(n) 可接受吗? A:重复多需考虑其他方案。

02.5.1.2-019 旋转数组题有哪些常见追问?

一句话结论

有重复怎么办、断点在哪、无旋转是否兼容、为什么与右界比较、最坏复杂度、能否求旋转次数;都围绕分段判定与等值退化回答。

概念解释

  • 重复处理。
  • 断点定位。
  • 复杂度口径。

原理流程

  1. 说明分段判定。
  2. 说明等值退化。
  3. 报复杂度。

代码 / 图示

重复 → 收缩退化
断点 → 最小值位置

常见误区

  • 误区:追问重复时仍答 O(log n);正解:说明最坏 O(n)。
  • 误区:说不清比较参照;正解:固定 mid 与 r。

追问

  • Q:两数相乘旋转? A:与二分无关。
  • Q:环形有序数组? A:同旋转模型。

02.5.1.2-020 部分有序二分常见变体有哪些?

一句话结论

旋转查找、找最小值、旋转次数、山峰数组、局部峰谷、两段拼接有序数组;主线是识别有序段 + 端点夹逼 + 保留候选侧。

概念解释

  • 框架:分段二分。
  • 变体:峰谷/拼接。
  • 场景包装。

原理流程

  1. 识别单调段。
  2. 判定归属。
  3. 收缩区间。

代码 / 图示

分段有序 → 夹逼 → 折半

常见误区

  • 误区:变体题脱离二分框架;正解:先找可排除一半的性质。
  • 误区:无序段端点参与夹逼;正解:只在有序段内判定。

追问

  • Q:山峰数组峰值(LC 162)? A:比较中点与右侧,高处侧收缩。
  • Q:拼接有序数组合并? A:归并思路见 02.5.2.3。