普通数组
更新: 9/2/2025 字数: 0 字 时长: 0 分钟
最大子数组和
java
/**
* <p>此方法使用动态规划来找到数组中具有最大和的连续子数组。</p>
* <p>核心思想是：遍历数组，对于每个元素 {@code nums[i]}，我们有两个选择来构建以 {@code nums[i]} 结尾的子数组：</p>
* <ol>
* <li>将 {@code nums[i]} 添加到前面子数组的最大和中（如果这个和是正的）。</li>
* <li>重新开始一个新的子数组，只包含 {@code nums[i]}。</li>
* </ol>
* <p>我们选择能使当前子数组和更大的那个选项，并不断更新全局的最大和。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>初始化变量：</strong>
* <ul>
* <li>{@code maxSum}：用于存储到目前为止找到的全局最大子数组和，初始化为数组的第一个元素 {@code nums[0]}。</li>
* <li>{@code currentSum}：用于存储以当前遍历到的元素 {@code nums[i]} 结尾的最大子数组和，初始化为数组的第一个元素 {@code nums[0]}。</li>
* </ul>
* </li>
* <li><strong>遍历数组：</strong>
* <ul>
* <li>从数组的第二个元素开始（索引 {@code i = 1}）遍历到数组的最后一个元素。</li>
* <li>对于每个元素 {@code nums[i]}：
* <ul>
* <li>更新 {@code currentSum}：比较两个值：
* <ul>
* <li>{@code nums[i]}：表示以 {@code nums[i]} 开始的新子数组。</li>
* <li>{@code currentSum + nums[i]}：表示将 {@code nums[i]} 加入到以 {@code nums[i-1]} 结尾的最大子数组中。</li>
* </ul>
* 选择这两者中较大的一个作为新的 {@code currentSum}。
* 等价于：{@code currentSum = Math.max(nums[i], currentSum + nums[i])}。
* </li>
* <li>更新 {@code maxSum}：比较当前的 {@code currentSum} 和全局的 {@code maxSum}，将较大的值赋给 {@code maxSum}。
* 等价于：{@code maxSum = Math.max(maxSum, currentSum)}。
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li>遍历结束后，返回 {@code maxSum}。</li>
* </ol>
*
* <h3>动态规划状态转移方程：</h3>
* <p>定义 {@code dp[i]} 为以 {@code nums[i]} 结尾的最大连续子数组和。</p>
* <p>{@code dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0)}</p>
* <p>或者更简洁地：{@code dp[i] = Math.max(nums[i], dp[i-1] + nums[i])}</p>
* <p>最终结果是所有 {@code dp[i]} 中的最大值。</p>
* <p>在实际实现中，我们不需要一个完整的 {@code dp} 数组，只需要一个变量 {@code currentSum} 来表示 {@code dp[i-1]}，从而将空间复杂度优化到 {@code O(1)}。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>我们只遍历数组一次。</li>
* <li>每次迭代中的操作（比较和加法）都是 {@code O(1)}。</li>
* <li>因此，总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>除了存储输入数组所需的空间外，只使用了常数个额外变量 ({@code maxSum}, {@code currentSum})。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @return 数组中具有最大和的连续子数组的最大和。
*/
public int maxSubArray(int[] nums) {
// maxSum 存储全局最大子数组和
int maxSum = nums[0];
// currentSum 存储以当前元素结尾的最大子数组和
int currentSum = nums[0];
// 从数组的第二个元素开始遍历
for (int i = 1; i < nums.length; i++) {
// 对于当前元素 nums[i]，以它结尾的最大子数组和有两种可能：
// 1. 包含 nums[i-1] 之前的所有元素，即 currentSum + nums[i]
// 2. 只包含 nums[i] 自己，形成一个新的子数组
// 我们选择其中较大的一个作为新的 currentSum
currentSum = Math.max(nums[i], currentSum + nums[i]);
// 更新全局最大子数组和
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}合并区间
java
/**
* <p>此方法使用排序和迭代遍历的方式来合并重叠的区间。</p>
* <p>核心思想是：首先对所有区间按照它们的起始点进行排序。排序后，重叠的区间会相邻。
* 然后，我们遍历排序后的区间，将它们逐个合并。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>预处理与边界检查：</strong>
* <ul>
* <li>如果输入的 {@code intervals} 数组为空或只包含一个区间，则无需合并，直接返回原数组。</li>
* </ul>
* </li>
* <li><strong>排序：</strong>
* <ul>
* <li>对 {@code intervals} 数组按照每个区间的起始点（即 {@code intervals[i][0]}）进行升序排序。
* 如果起始点相同，可以按结束点排序，但通常只按起始点排序即可满足需求。
* 排序后，可以保证如果区间 A 和区间 B 可能重叠，且 A 在 B 之前，那么 A 的起始点一定小于等于 B 的起始点。
* </li>
* </ul>
* </li>
* <li><strong>遍历合并：</strong>
* <ul>
* <li>创建一个 {@link java.util.List} 来存储合并后的区间（因为最终合并后的区间数量不确定）。</li>
* <li>将排序后的第一个区间添加到 {@code mergedIntervals} 列表中作为当前正在处理的合并区间。</li>
* <li>从第二个区间开始遍历剩余的区间：
* <ul>
* <li>获取当前正在处理的合并区间 {@code lastMerged = mergedIntervals.get(mergedIntervals.size() - 1)}。</li>
* <li>获取当前遍历到的区间 {@code current = intervals[i]}。</li>
* <li><strong>判断是否重叠：</strong>
* <ul>
* <li>如果 {@code current[0] <= lastMerged[1]}，表示 {@code current} 与 {@code lastMerged} 重叠。
* <ul>
* <li>此时，需要更新 {@code lastMerged} 的结束点，取 {@code lastMerged[1]} 和 {@code current[1]} 中的较大值。
* {@code lastMerged[1] = Math.max(lastMerged[1], current[1])}。</li>
* </ul>
* </li>
* <li>如果 {@code current[0] > lastMerged[1]}，表示 {@code current} 与 {@code lastMerged} 不重叠。
* <ul>
* <li>此时，{@code lastMerged} 已经合并完毕，将 {@code current} 添加到 {@code mergedIntervals} 中，作为新的当前正在处理的合并区间。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>将 {@code mergedIntervals} 列表转换为二维数组并返回。</li>
* </ul>
* </li>
* </ol>
*
* <h3>示例：</h3>
* <p>输入：{@code [[1,3],[2,6],[8,10],[15,18]]}</p>
* <ol>
* <li><strong>排序后：</strong> {@code [[1,3],[2,6],[8,10],[15,18]]} (本例中已排序)</li>
* <li><strong>初始化：</strong> {@code mergedIntervals = [[1,3]]}</li>
* <li><strong>遍历：</strong>
* <ul>
* <li>当前区间 {@code [2,6]}：与 {@code [1,3]} 重叠 (2 <= 3)。合并为 {@code [1,6]}。
* {@code mergedIntervals = [[1,6]]}</li>
* <li>当前区间 {@code [8,10]}：与 {@code [1,6]} 不重叠 (8 > 6)。添加 {@code [8,10]}。
* {@code mergedIntervals = [[1,6],[8,10]]}</li>
* <li>当前区间 {@code [15,18]}：与 {@code [8,10]} 不重叠 (15 > 10)。添加 {@code [15,18]}。
* {@code mergedIntervals = [[1,6],[8,10],[15,18]]}</li>
* </ul>
* </li>
* <li><strong>返回：</strong> {@code [[1,6],[8,10],[15,18]]}</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N log N)}。
* <ul>
* <li>排序操作是 {@code O(N log N)}，其中 {@code N} 是区间的数量。</li>
* <li>遍历合并操作是 {@code O(N)}，因为每个区间只被处理一次。</li>
* <li>因此，总时间复杂度由排序决定，为 {@code O(N log N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>存储排序后的区间可能需要 {@code O(log N)} (如果原地排序) 或 {@code O(N)} (如果使用额外的数组进行排序)。
* Java 的 {@code Arrays.sort} 对于对象数组是 {@code O(log N)} 栈空间，对于基本类型是 {@code O(N)}。
* </li>
* <li>存储合并后的结果列表 {@code mergedIntervals} 最坏情况下（没有区间重叠）需要 {@code O(N)} 的空间。</li>
* <li>因此，总空间复杂度为 {@code O(N)}。</li>
* </ul>
* </li>
* </ul>
*
* @param intervals 表示若干个区间的集合，其中单个区间为 {@code [starti, endi]}。
* @return 一个不重叠的区间数组，该数组恰好覆盖输入中的所有区间。
*/
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals; // 如果没有或只有一个区间，无需合并，直接返回
}
// 1. 按照区间的起始点进行排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0]; // 按照起始点升序排序
}
});
List<int[]> mergedIntervals = new ArrayList<>();
// 2. 将第一个区间添加到结果列表中作为当前正在合并的区间
mergedIntervals.add(intervals[0]);
// 3. 遍历剩余的区间
for (int i = 1; i < intervals.length; i++) {
// 获取结果列表中最后一个已合并的区间
int[] lastMerged = mergedIntervals.getLast();
// 获取当前遍历到的区间
int[] current = intervals[i];
// 判断是否重叠：如果当前区间的起始点小于等于上一个合并区间的结束点
if (current[0] <= lastMerged[1]) {
// 重叠，更新上一个合并区间的结束点，取两者的最大值
lastMerged[1] = Math.max(lastMerged[1], current[1]);
} else {
// 不重叠，将当前区间添加到结果列表中，作为新的待合并区间
mergedIntervals.add(current);
}
}
// 将 List 转换为二维数组并返回
return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
}轮转数组
java
/**
* <p>方法一：使用额外数组进行轮转。</p>
* <p>思路：创建一个与原数组等长的新数组 {@code newArr}。
* 对于原数组 {@code nums} 中的每个元素 {@code nums[i]}，
* 计算它轮转 {@code k} 个位置后的新索引 {@code (i + k) % n}，并将其放入 {@code newArr} 中。
* 最后，将 {@code newArr} 的内容复制回 {@code nums}。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li>获取数组长度 {@code n}。</li>
* <li>创建新数组 {@code newArr}，大小为 {@code n}。</li>
* <li>遍历原数组 {@code nums}，对于每个索引 {@code i}：
* <ul>
* <li>计算新位置 {@code newIndex = (i + k) % n}。</li>
* <li>将 {@code nums[i]} 赋值给 {@code newArr[newIndex]}。</li>
* </ul>
* </li>
* <li>将 {@code newArr} 的所有元素复制回 {@code nums}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>一次遍历填充 {@code newArr}。</li>
* <li>一次遍历将 {@code newArr} 复制回 {@code nums}（或者使用 {@code System.arraycopy} 也是 {@code O(n)}）。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>需要一个额外的数组 {@code newArr}，其大小与输入数组相同。</li>
* </ul>
* </li>
* </ul>
*/
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return;
}
// 确保 k 在 [0, n-1] 范围内，简化后续模运算
k = k % n;
if (k == 0) { // 如果 k 是 n 的倍数，相当于不旋转
return;
}
int[] newArr = new int[n];
for (int i = 0; i < n; i++) {
// 原位置 i 的元素，轮转 k 个位置后，新位置是 (i + k) % n
newArr[(i + k) % n] = nums[i];
}
// 将新数组的元素复制回原数组
System.arraycopy(newArr, 0, nums, 0, n);
}java
/**
* <p>方法二：环状替换（Juggling Algorithm），原地算法。</p>
* <p>思路：利用一个或多个环来移动元素。
* 从索引 {@code start = 0} 开始，将 {@code nums[start]} 移动到它轮转后的位置 {@code (start + k) % n}。
* 然后，将 {@code nums[(start + k) % n]} 原来的值移动到它轮转后的位置，依此类推。
* 这个过程会形成一个环，直到我们回到 {@code start}。
* 为了确保所有元素都被移动，我们需要执行 {@code gcd(n, k)}（{@code n} 和 {@code k} 的最大公约数）次这样的“链式”替换。
* 每个链的起始点是 {@code 0, 1, ..., gcd(n, k) - 1}。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li>获取数组长度 {@code n}。</li>
* <li>确保 {@code k} 在 [0, n-1] 范围内，{@code k = k % n}。</li>
* <li>如果 {@code k == 0}，直接返回。</li>
* <li>初始化 {@code count = 0}，用于记录已移动的元素数量。</li>
* <li>从 {@code start = 0} 开始循环，直到 {@code start < n}。
* <ul>
* <li>将 {@code current = start} 和 {@code prev = nums[start]} 赋值。</li>
* <li>开始内层循环，直到回到 {@code start}：
* <ul>
* <li>计算下一个位置 {@code next = (current + k) % n}。</li>
* <li>保存 {@code nums[next]} 的值到 {@code temp}。</li>
* <li>将 {@code prev}（上一个位置的元素）放入 {@code nums[next]}。</li>
* <li>更新 {@code prev = temp}。</li>
* <li>更新 {@code current = next}。</li>
* <li>递增 {@code count}。</li>
* </ul>
* </li>
* <li>外层循环的 {@code start} 递增。如果 {@code count == n}，说明所有元素都已移动，可以提前结束。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>每个元素恰好被访问和移动一次。总共 {@code n} 次移动。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外变量，是原地操作。</li>
* </ul>
* </li>
* </ul>
*
* <p><strong>GCD 的作用：</strong></p>
* <p>{@code GCD(n, k)} 决定了有多少个独立的环。例如，如果 {@code n=6, k=2}：
* <ul>
* <li>从 0 开始：0 -> 2 -> 4 -> 0 (环 1)</li>
* <li>从 1 开始：1 -> 3 -> 5 -> 1 (环 2)</li>
* </ul>
* {@code GCD(6, 2) = 2}，所以有两个环。
* 如果 {@code GCD(n, k) = 1} (即 {@code n} 和 {@code k} 互质)，则只有一个环，所有元素在一个链中移动。</p>
*/
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return;
}
k = k % n; // 确保 k 在 [0, n-1] 范围内
if (k == 0) {
return;
}
int count = 0; // 记录已经移动的元素数量，当 count == n 时结束
for (int start = 0; count < n; start++) { // 从不同的起始点开始处理不同的环
int current = start;
int prev = nums[start]; // 保存当前位置的元素，准备放入下一个位置
do {
int next = (current + k) % n; // 计算下一个位置
int temp = nums[next]; // 保存下一个位置的元素，准备成为新的 prev
nums[next] = prev; // 将上一个位置的元素放入当前计算的下一个位置
prev = temp; // 更新 prev 为之前保存的下一个位置的元素
current = next; // 更新 current 为下一个位置
count++; // 移动的元素数量加一
} while (start != current); // 循环直到回到起始点，完成一个环的移动
}
}java
/**
* <p>方法三：数组翻转（Reverse Algorithm），原地算法。</p>
* <p>思路：利用三次数组翻转来实现轮转操作。
* 假设数组长度为 {@code n}，向右轮转 {@code k} 个位置。
* 实际上是把数组的最后 {@code k} 个元素移到前面，把前面的 {@code n-k} 个元素移到后面。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li>获取数组长度 {@code n}。</li>
* <li>确保 {@code k} 在 [0, n-1] 范围内，{@code k = k % n}。</li>
* <li>如果 {@code k == 0}，直接返回。</li>
* <li><strong>第一次翻转：</strong> 翻转整个数组 {@code nums[0...n-1]}。
* <p> 例如：{@code [1,2,3,4,5,6,7]} -> {@code [7,6,5,4,3,2,1]}</p>
* </li>
* <li><strong>第二次翻转：</strong> 翻转前 {@code k} 个元素 {@code nums[0...k-1]}。
* <p> 例如 (k=3)：{@code [7,6,5,4,3,2,1]} -> {@code [5,6,7,4,3,2,1]}</p>
* </li>
* <li><strong>第三次翻转：</strong> 翻转后 {@code n-k} 个元素 {@code nums[k...n-1]}。
* <p> 例如 (n-k=4)：{@code [5,6,7,4,3,2,1]} -> {@code [5,6,7,1,2,3,4]}</p>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>每个翻转操作都是 {@code O(n)}（或 {@code O(k)} / {@code O(n-k)}），总共三次线性遍历。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外变量，是原地操作。</li>
* </ul>
* </li>
* </ul>
*/
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return;
}
k = k % n; // 确保 k 在 [0, n-1] 范围内
if (k == 0) {
return;
}
// 1. 翻转整个数组
reverse(nums, 0, n - 1); // [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
// 2. 翻转前 k 个元素
reverse(nums, 0, k - 1); // [7,6,5,4,3,2,1] (k=3) -> [5,6,7,4,3,2,1]
// 3. 翻转后 n-k 个元素
reverse(nums, k, n - 1); // [5,6,7,4,3,2,1] (n-k=4) -> [5,6,7,1,2,3,4]
}
/**
* 辅助函数：翻转数组中指定范围 [start, end] 的元素。
*
* @param nums 数组。
* @param start 翻转起始索引。
* @param end 翻转结束索引。
*/
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}除自身以外数组的乘积
java
/**
* <p>此方法解决“除自身以外数组的乘积”问题，遵循不使用除法和 O(N) 时间复杂度的要求。</p>
* <p>核心思想是：对于 {@code answer[i]}，它等于 {@code nums[i]} 左边的所有元素的乘积乘以 {@code nums[i]} 右边的所有元素的乘积。</p>
* <p>我们可以通过两次遍历来分别计算每个位置的左边乘积和右边乘积，然后将它们相乘。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>初始化 {@code answer} 数组：</strong>
* <ul>
* <li>创建一个与 {@code nums} 数组等长的新数组 {@code answer}。</li>
* </ul>
* </li>
* <li><strong>第一次遍历（计算左边乘积）：</strong>
* <ul>
* <li>从左到右遍历数组 {@code nums}。</li>
* <li>维护一个变量 {@code leftProduct}，表示当前元素左边所有元素的乘积。</li>
* <li>对于 {@code answer[i]}：
* <ul>
* <li>初始化 {@code answer[0] = 1} (因为 {@code nums[0]} 左边没有元素，乘积为 1)。</li>
* <li>对于 {@code i > 0}，{@code answer[i]} 存储 {@code nums[0] * nums[1] * ... * nums[i-1]}。
* 这可以通过 {@code leftProduct = leftProduct * nums[i-1]} 来累积。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>第二次遍历（计算右边乘积并合并结果）：</strong>
* <ul>
* <li>从右到左遍历数组 {@code nums}。</li>
* <li>维护一个变量 {@code rightProduct}，表示当前元素右边所有元素的乘积。</li>
* <li>对于 {@code answer[i]}：
* <ul>
* <li>初始化 {@code rightProduct = 1}。</li>
* <li>对于 {@code i < n - 1}，{@code answer[i]} 还需要乘以 {@code nums[i+1] * nums[i+2] * ... * nums[n-1]}。
* 这可以通过 {@code rightProduct = rightProduct * nums[i+1]} 来累积。</li>
* <li>最终的 {@code answer[i]} = (左边乘积) * (右边乘积)。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>具体步骤与示例（以 {@code nums = [1,2,3,4]} 为例）：</h3>
* <ol>
* <li><strong>初始化：</strong> {@code answer = [0,0,0,0]}</li>
* <li><strong>第一次遍历 (计算左边乘积，并存入 {@code answer} 数组)：</strong>
* <ul>
* <li>{@code leftProduct = 1}</li>
* <li>{@code i = 0}: {@code answer[0] = leftProduct} (即 1)。{@code leftProduct = leftProduct * nums[0]} (即 1 * 1 = 1)。
* 此时 {@code answer = [1,0,0,0]}</li>
* <li>{@code i = 1}: {@code answer[1] = leftProduct} (即 1)。{@code leftProduct = leftProduct * nums[1]} (即 1 * 2 = 2)。
* 此时 {@code answer = [1,1,0,0]}</li>
* <li>{@code i = 2}: {@code answer[2] = leftProduct} (即 2)。{@code leftProduct = leftProduct * nums[2]} (即 2 * 3 = 6)。
* 此时 {@code answer = [1,1,2,0]}</li>
* <li>{@code i = 3}: {@code answer[3] = leftProduct} (即 6)。{@code leftProduct = leftProduct * nums[3]} (即 6 * 4 = 24)。
* 此时 {@code answer = [1,1,2,6]}</li>
* </ul>
* 至此，{@code answer} 数组中存储了每个元素左边所有元素的乘积：{@code [1, 1, 2, 6]}。
* </li>
* <li><strong>第二次遍历 (计算右边乘积，并与 {@code answer} 中已有的左边乘积相乘)：</strong>
* <ul>
* <li>{@code rightProduct = 1}</li>
* <li>{@code i = 3}: {@code answer[3] = answer[3] * rightProduct} (即 6 * 1 = 6)。{@code rightProduct = rightProduct * nums[3]} (即 1 * 4 = 4)。
* 此时 {@code answer = [1,1,2,6]}</li>
* <li>{@code i = 2}: {@code answer[2] = answer[2] * rightProduct} (即 2 * 4 = 8)。{@code rightProduct = rightProduct * nums[2]} (即 4 * 3 = 12)。
* 此时 {@code answer = [1,1,8,6]}</li>
* <li>{@code i = 1}: {@code answer[1] = answer[1] * rightProduct} (即 1 * 12 = 12)。{@code rightProduct = rightProduct * nums[1]} (即 12 * 2 = 24)。
* 此时 {@code answer = [1,12,8,6]}</li>
* <li>{@code i = 0}: {@code answer[0] = answer[0] * rightProduct} (即 1 * 24 = 24)。{@code rightProduct = rightProduct * nums[0]} (即 24 * 1 = 24)。
* 此时 {@code answer = [24,12,8,6]}</li>
* </ul>
* </li>
* <li><strong>返回：</strong> {@code [24,12,8,6]}</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>第一次遍历需要 {@code O(N)} 时间。</li>
* <li>第二次遍历需要 {@code O(N)} 时间。</li>
* <li>总时间复杂度为 {@code O(N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)} (不包括返回结果数组)。
* <ul>
* <li>根据题目要求，返回的结果数组不计入额外空间复杂度。</li>
* <li>我们只使用了几个常数级别的变量 {@code leftProduct} 和 {@code rightProduct}。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @return 数组 {@code answer}，其中 {@code answer[i]} 等于 {@code nums} 中除 {@code nums[i]} 之外其余各元素的乘积。
*/
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
// answer 数组用于存储最终结果
int[] answer = new int[n];
// 1. 第一次遍历：计算每个元素左边的所有元素的乘积
// 对于 answer[i]，首先存储的是 nums[0]...nums[i-1] 的乘积
int leftProduct = 1;
for (int i = 0; i < n; i++) {
answer[i] = leftProduct; // answer[i] 暂时存储了其左边元素的乘积
leftProduct *= nums[i]; // 更新 leftProduct，用于下一个元素的左边乘积计算
}
// 此时 answer 数组：[1, nums[0], nums[0]*nums[1], nums[0]*nums[1]*nums[2], ...]
// 2. 第二次遍历：计算每个元素右边的所有元素的乘积，并与已有的左边乘积相乘
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
// answer[i] = (左边乘积) * (右边乘积)
answer[i] *= rightProduct; // answer[i] 乘以其右边元素的乘积
rightProduct *= nums[i]; // 更新 rightProduct，用于下一个元素的右边乘积计算
}
return answer;
}缺失的第一个正数
java
/**
* <p>此方法解决“缺失的第一个正数”问题，要求时间复杂度 O(N) 和空间复杂度 O(1)。</p>
* <p>核心思想是利用原地哈希（或称为桶排序思想）：将数组本身作为哈希表，
* 尝试将每个正整数 {@code x} 放到它“应该在”的位置 {@code nums[x-1]}。</p>
* <p>例如，如果数组中有数字 {@code 1}，它应该被放在索引 {@code 0} 的位置；
* 如果有数字 {@code 2}，它应该被放在索引 {@code 1} 的位置，依此类推。</p>
* <p>只有在 {@code 1 <= x <= n} (其中 {@code n} 是数组长度) 的范围内，数字才有可能被正确放置。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>原地放置阶段 (Pre-processing / In-place Hashing):</strong>
* <ul>
* <li>遍历数组 {@code nums}，从索引 {@code i = 0} 到 {@code n - 1}。</li>
* <li>对于每个 {@code nums[i]}，执行一个内层 {@code while} 循环：
* <ul>
* <li>条件：当前 {@code nums[i]} 必须满足以下三点：
* <ul>
* <li>{@code nums[i] > 0}：必须是正数。</li>
* <li>{@code nums[i] <= n}：必须在有效索引范围内 (1 到 n)。</li>
* <li>{@code nums[i] != nums[nums[i] - 1]}：它不在其正确的位置上。
* (例如，如果 {@code nums[i]=3}，它应该在 {@code nums[2]}。如果 {@code nums[2]} 已经是 {@code 3}，则说明它已在位。)</li>
* </ul>
* </li>
* <li>如果满足上述条件，则交换 {@code nums[i]} 和 {@code nums[nums[i] - 1]}。
* 这是因为 {@code nums[i]} 这个值应该放在 {@code nums[nums[i]-1]} 的位置。
* 交换后，{@code nums[i]} 变成了原来 {@code nums[nums[i]-1]} 的值，这个新值可能也需要被处理。</li>
* <li>{@code while} 循环会一直进行，直到 {@code nums[i]} 不满足条件，即：
* <ul>
* <li>它不是一个有效的正整数（{@code <= 0} 或 {@code > n}）。</li>
* <li>或者它已经位于其正确的位置上。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>查找缺失阶段 (Finding the Missing Number):</strong>
* <ul>
* <li>在完成原地放置后，数组中所有在 {@code 1} 到 {@code n} 范围内的正整数都尽可能地被放置到其对应的索引位置上。</li>
* <li>再次遍历数组 {@code nums}，从索引 {@code i = 0} 到 {@code n - 1}。</li>
* <li>如果发现 {@code nums[i] != i + 1}，那么 {@code i + 1} 就是缺失的第一个正整数。</li>
* <li>如果遍历完整个数组都没有发现不匹配的，说明 {@code 1} 到 {@code n} 的所有正整数都存在于数组中，
* 那么缺失的第一个正整数就是 {@code n + 1}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>外层循环遍历 {@code N} 次。</li>
* <li>内层 {@code while} 循环看起来是嵌套的，但每个元素最多被交换两次 (一次从错误位置移出，一次被放到正确位置)。
* 总的交换次数和移动次数是线性的，因此总时间复杂度是 {@code O(N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>我们只使用了常数个额外变量，在原数组上进行操作。</li>
* </ul>
* </li>
* </ul>
*/
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 阶段 1: 将正整数放置到正确的位置
// 即，将数字 x 放到索引 x-1 的位置上
for (int i = 0; i < n; i++) {
// 当 nums[i] 满足以下条件时，进行交换操作：
// 1. nums[i] 是正数
// 2. nums[i] 不超过数组长度 n (因为它应该放到索引 nums[i]-1，不能越界)
// 3. nums[i] 不在它应该在的位置上 (即 nums[i] != nums[nums[i]-1])
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
// 计算 nums[i] 应该去的正确索引
int correctIndex = nums[i] - 1;
// 交换 nums[i] 和 nums[correctIndex]
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
// 交换后，新的 nums[i] 仍然可能需要被处理，所以继续内层 while 循环
}
}
// 阶段 2: 查找第一个不匹配的索引，即为缺失的第一个正数
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1; // 找到了缺失的第一个正数
}
}
// 如果遍历完所有元素，都匹配 (即 nums[i] == i + 1)，
// 说明 1 到 n 的所有正整数都存在，那么缺失的第一个正数就是 n + 1
return n + 1;
}贡献者
LI SIR