- 第一题：
- 二分查找
- 第二题
- 方法一：排序后遍历
- - 方法二：直接统计数量
- 第三题
- 第四题
第一题：我这里第二个好像是7.2号的题，看错题了。
最后一题有点难度，我不太会，就不往笔记里面写了。
高校算法学习社区
- 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int l=0,r= nums.length-1;
while (r>=l){
int mid=(l+r)/2;
if (target==nums[mid]){
return mid;
}else if (target>nums[mid]){
l=mid+1;
}else {
r=mid-1;
}
}
return -1;
}
}
思路：
二分查找在升序数组nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：
如果 nums[i]=target，则下标 i 即为要寻找的下标；
如果nums[i]>target，则 target 只可能在下标 i 的左侧；
如果 [i] < nums[i] 基于上述事实，可以在有序数组中使用二分查找寻找目标值。 二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 [mid] 和target 的大小，如果相等则mid 即为要寻找的下标，如果不相等则根据 [mid] 和 target 的大小关系将查找范围缩小一半。 由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(log n)O(logn)，其中 nn 是数组的长度。 二分查找的条件是查找范围不为空，即 left≤right。如果target 在数组中，二分查找可以保证找到 target，返回target 在数组中的下标。如果 target 不在数组中，则当 left>right 时结束查找，返回 −1。 这是力扣的官方题解，我下面题解都尽量用官方的，以免哪里出错误导你们了，毕竟我对算法这里也是小白，哈哈哈。 这是我自己的提交界面。 思路与算法 我们首先按要求对 nums 数组升序排序，随后从左到右遍历数组中的所有元素，并按顺序记录所有数值等于 target 的元素的下标。这样我们可以保证记录的下标数组中的下标（如果存在）必定按照递增顺序排列。 最后，如果符合要求的下标存在，我们返回记录的下标数组作为答案；如果不存在，我们返回空数组即可。 思路与算法 我们也可以不对数组排序来构造目标下标。 在排序后数组中，这些数值等于 target 的元素的下标（如果存在）一定是连续的。因此，我们可以通过寻找目标下标的左边界（即最小值，如果存在，下同）和目标下标的数量来构造目标下标数组。 由于数组是升序排序的，数值等于target 的元素一定在数值小于target 的元素的右侧，因此目标下标的左边界即为数组中数值小于 target 的元素数量。而目标下标的数量即为数组中数值等于 target 的元素数量。 我们遍历未排序的数组，计算数值小于target 的元素数量 cnt1与数值等于 target 的元素数量 cnt2，则此时目标下标即为 [cnt1,cnt1 +cnt 2) 左闭右开区间内的所有整数。我们按照递增的顺序构造对应的下标数组（可能为空）并返回即可。 力扣官方题解 给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。 这是我的代码 来源：力扣（LeetCode） 题解：
力扣官方题解
目标下标 是一个满足 nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-target-indices-after-sorting-arraypublic class Solution {
public List
复杂度分析
- 方法二：直接统计数量
官方的题解是只有C++，Python版的，可以参考一下，我个人做这题时是先新建一个链表 res，用于存储nums数组中的目标下标，利用for循环嵌套if条件句来实现目标下标的存储，如果没有，返回res即可。
易错点：
1.新建的是链表而不是数组，一定要审清楚题
2.最后返回的时候如果没有目标下标，直接返回res即可。
我当时就是脑子蒙了，居然去return null；别跟我一样啊。
返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-increment-to-make-array-unique
public class Solution5 {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
//操作次数
int fre = 0;
//遍历数组，若当前元素小于等于它的前一个元素，则将其变为前一个数+1
for (int i = 1; i < nums.length; i++) {
int cur=nums[i];
if(cur<=nums[i-1]){
fre+=nums[i-1]-cur+1;
nums[i] = nums[i-1]+1;
}
}
return fre;
}
}
我这里是先对数组进行排序，然后遍历，如果数组的当前值小于等于前一个值，就让当前值 等于前一个值加一，记录操作次数，最后返回。
力扣官方题解
https://leetcode.cn/problems/minimum-increment-to-make-array-unique/solution/shi-shu-zu-wei-yi-de-zui-xiao-zeng-liang-by-leet-2/
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
链接：https://leetcode.cn/problems/find-the-duplicate-numberclass Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
