✨前言
美好的一天从算法刷题开始，今天的四题准备就绪。
1.二分查找
2.找出数组排序后的目标下标
3.寻找重复数
4.Binary Deque
小伙伴们一起学习吧！！😎
文章目录
一、二分查找
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
思路详解
首先呢，定义左边界和右边界，通过左右边界找到中间值，
如果中间值比目标值小，就把中间值的后一位下标设置为左边界，继续找中间值比较；
如果中间值比目标值大，就把中间值的前一位下标设置为右边界，继续找中间值比较。
直到找到目标值，如果找完没找到，就表示数组中没有目标值。
代码与结果
class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = (right - left) / 2 + left; int num = nums[mid]; if (num == target) { return mid; } else if (num > target) { right = mid - 1; } else { left = mid + 1; } } return -1; } }
‘
二、找出数组排序后的目标下标
题目描述
给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。
目标下标 是一个满足 nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-target-indices-after-sorting-array
思路详解
本题首先想到的就是，先建立一个空的res数组，通过排序后的数组进行遍历查找，找到就加到res中。
代码与结果
class Solution { public List<Integer> targetIndices(int[] nums, int target) { List<Integer> res = new ArrayList<Integer>(); Arrays.sort(nums); for(int i = 0 ; i < nums.length; i++){ if(nums[i] == target) res.add(i); } return res; } }
三、寻找重复数
题目描述
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-duplicate-number
思路详解
根据题意，我们首先拷贝一个临时数组，然后对其进行排序，由于只有一个是重复的整数，我们只需要进行循环遍历找到和前一个数相同的，直接输出就好。
代码与结果
class Solution { public int findDuplicate(int[] nums) { int[] temp = new int[nums.length]; for(int i = 0;i < nums.length; i++){ temp[i] = nums[i]; } Arrays.sort(temp); for(int j = 1;j < nums.length;j++){ if(temp[j] == temp[j - 1]) return temp[j]; } return 0; } }
✨总结
以上算法有的时间复杂度也是较高的，有更好方法的小伙伴欢迎评论区留言。
看到这里的小伙伴留个赞赞再走吧，欢迎一起讨论算法哦。🐳
😎The man who fears losing has already lost.
怕输的人已经输了。 - 《权力的游戏》😎
