芜湖网站建设公司,php图片展示网站,学校网站的作用和意义,南宁网站seo推广优化公司1.点名 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席#xff0c;请返回他的学号。
示例 1:
输入: records [0,1,2,3,5]
输出: 4示例 2:
输入: records [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7提示#xff1a;
1 records.le…1.点名 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席请返回他的学号。
示例 1:
输入: records [0,1,2,3,5]
输出: 4示例 2:
输入: records [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7提示
1 records.length 10000
1.1二分法查找 这是一个缺失数问题在给定的升序数组 records 中找出缺席同学的学号。数组 records 是由班级同学的学号组成的其中学号从 0 开始逐个递增仅有一位同学缺席。要找出缺席的学号我们可以借助 二分查找 的方法快速定位缺失位置。
解题思路
因为记录是升序的学号列表仅有一位学号缺失可以推断
如果数组中没有缺失数字那么 records[i] 应等于 i即每个索引位置的值与其索引相等。如果某个数字缺失则从缺失位置开始数组中的元素不再满足 records[i] i 关系而是比其索引值大 1。因此我们可以利用这一规律进行查找。
算法解析
使用二分查找的方式我们可以在对数时间复杂度 O(log n) 下找到缺失的学号
初始化左右指针将 i 设为 0左指针j 设为 records.length - 1右指针用于二分查找。循环查找在 i j 的条件下不断收缩查找范围。 计算中间位置 m (i j) / 2。检查 records[m] 的值 如果 records[m] m说明前面没有缺失元素当前索引 m 位置的值是正确的所以缺失的学号在右半部分。将 i 设为 m 1向右搜索。如果 records[m] ! m说明缺失学号在左半部分从当前 m 位置开始有不匹配的情况。将 j 设为 m - 1向左搜索。结束循环当 i 大于 j 时循环结束缺失的学号即为 i。
最终i 的位置就是缺失学号的位置。
复杂度分析
时间复杂度二分查找使得时间复杂度为 O(log n)适用于数据规模较大的情况。空间复杂度仅使用常数级别的额外空间空间复杂度为 O(1)。
代码示例
class Solution {public int takeAttendance(int[] records) {// 初始化左右指针int i 0, j records.length - 1;// 使用二分查找寻找缺失的学号while(i j) {// 计算中间位置 mint m (i j) / 2;// 判断中间位置 m 是否与学号对应if(records[m] m) {// 如果 records[m] m说明左侧都正常匹配缺失学号在右侧i m 1; // 将左指针移到右半部分} else {// 如果 records[m] ! m说明缺失学号在左半部分j m - 1; // 将右指针移到左半部分}}// 最终 i 的位置即为缺失的学号return i;}
}2.查找总价值为目标值的两个商品 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。
示例 1
输入price [3, 9, 12, 15], target 18
输出[3,15] 或者 [15,3]示例 2
输入price [8, 21, 27, 34, 52, 66], target 61
输出[27,34] 或者 [34,27]提示
1 price.length 10^51 price[i] 10^61 target 2*10^6
2.1双指针检索
这是一个典型的双指针问题因为数组 price 已经是升序排列所以可以使用双指针快速查找两个数的和为 target 的组合。下面是解题思路、算法流程及复杂度分析。
解题思路 双指针从数组的两端开始逐步缩小范围利用排序数组的特性进行查找。 若两个指针指向的元素之和小于 target则需要更大的和因此将左指针右移。若和大于 target则需要更小的和因此将右指针左移。当和等于 target 时找到解。 提前返回找到符合条件的两个数后立即返回结果数组 [price[i], price[j]]这样可以保证时间效率。
算法解析
初始化定义两个指针 i 和 j分别指向数组的首尾位置。循环条件在 i j 的条件下进行迭代 计算 price[i] price[j] 的和 s。比较 s 和 target 如果 s target返回 [price[i], price[j]]。如果 s target左指针 i 右移增加和的值。如果 s target右指针 j 左移减小和的值。返回结果若循环结束仍未找到则返回空数组 []。
复杂度分析
时间复杂度O(N)其中 N 为数组 price 的长度。双指针仅需线性遍历一次数组。空间复杂度O(1)仅使用了常数级的额外空间。
代码示例
class Solution {public int[] twoSum(int[] price, int target) {// 初始化左右指针int i 0, j price.length - 1;// 使用双指针查找两个和为 target 的数while (i j) {// 计算当前左右指针指向元素的和int s price[i] price[j];// 判断当前和 s 是否等于目标 targetif (s target) {// 若 s 小于 target说明和偏小需要增大和// 将左指针右移i;} else if (s target) {// 若 s 大于 target说明和偏大需要减小和// 将右指针左移j--;} else {// 若 s 等于 target找到符合条件的组合立即返回return new int[] { price[i], price[j] };}}// 若未找到符合条件的组合返回空数组return new int[0];}
}3.文件组合 待传输文件被切分成多个部分按照原排列顺序每部分文件编号均为一个 正整数至少含有两个文件。传输要求为连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。
注意返回时需遵循以下规则
每种组合按照文件编号 升序 排列不同组合按照第一个文件编号 升序 排列。
示例 1
输入target 12
输出[[3, 4, 5]]
解释在上述示例中存在一个连续正整数序列的和为 12为 [3, 4, 5]。示例 2
输入target 18
输出[[3,4,5,6],[5,6,7]]
解释在上述示例中存在两个连续正整数序列的和分别为 18分别为 [3, 4, 5, 6] 和 [5, 6, 7]。提示
1 target 10^5
3.1滑动窗口 这是一个寻找连续正整数序列的和等于指定目标值 target 的问题。我们可以使用双指针滑动窗口的方法来高效地查找所有符合条件的组合。下面是解题思路、算法流程和复杂度分析。
解题思路
双指针法使用两个指针 i 和 j 来表示当前正在考虑的连续正整数的起始和结束位置。序列和的计算维护一个当前和 s初始为 3即 1 2表示 i1 和 j2 的和。遍历和调整 如果当前和 s 等于目标 target则记录下当前的连续整数序列。如果当前和 s 大于或等于目标 target则通过移动左指针 i 来减小和。如果当前和 s 小于目标 target则通过移动右指针 j 来增大和。
算法流程 初始化 i 为 1表示当前序列的起始位置。j 为 2表示当前序列的结束位置。s 为 3即 i 和 j 所指元素的和。使用一个列表 res 来存储符合条件的组合。 双指针循环 当 i 小于 j 时进行循环 如果 s 等于 target记录下从 i 到 j 的连续整数。如果 s 大于或等于 target将 s 减去 i 并将 i 右移。如果 s 小于 target将 j 右移并更新 s。 返回结果 将列表 res 转换为二维数组返回。
复杂度分析
时间复杂度O(N)其中 N 是目标 target 的值。双指针会遍历连续的正整数并调整整体复杂度为线性。空间复杂度O(M)其中 M 是存储符合条件组合的个数。由于使用了额外的列表来存储结果空间复杂度为线性。
import java.util.ArrayList;
import java.util.List;class Solution {public int[][] fileCombination(int target) {// 初始化双指针int i 1, j 2, s 3; // s 为当前连续正整数和Listint[] res new ArrayList(); // 存储结果// 双指针查找while (i j) {if (s target) {// 找到符合条件的组合记录下当前的连续正整数int[] ans new int[j - i 1];for (int k i; k j; k)ans[k - i] k; // 填充组合res.add(ans); // 添加到结果列表}// 调整指针if (s target) {s - i; // 减去左边的数字i; // 左指针右移} else {j; // 右指针右移s j; // 增加右边的数字}}// 返回结果数组return res.toArray(new int[0][]);}
}
