营销网站服务器,郑州金水区,平凉哪有做网站的,c2c网站制作用JAVA代码编写
704. 二分查找
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12]…用JAVA代码编写
704. 二分查找
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
文章讲解https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html 视频讲解https://www.bilibili.com/video/BV1fA4y1o715
思路 已知输入的数组是有序的我们的目标是找到target的元素。二分查找就是将整个数组划分连个数组将target与中间索引的值进行比较确定target是在左边还是右边一直找下去直到中间索引与target相等就找到了。
复杂度分析
时间复杂度 O(logN),其中 N 是数组的长度。空间复杂度O(1)
方法一[left,right]
class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target nums[0] || target nums[nums.length - 1]) {return -1;}int left 0, right nums.length - 1;while (left right) {//[left,right]int mid left ((right - left) 1);//相当于mid(leftright)/2if (nums[mid] target)return mid;else if (nums[mid] target)//目标在右边改变左区间left mid 1;//因为索引为mid的值小于目标所以目标索引肯定不是mid是他右边一个else if (nums[mid] target)//目标在左边改变右区间right mid - 1;}return -1;}public static void main(String[] args) {int[] nums{-1,0,3,5,9,12};Solution s1 new Solution();System.out.println(s1.search1(nums,9));}}方法二[left,right)
class Solution {public int search(int[] nums, int target) {int left 0, right nums.length;//区间左闭右开所以right需要取数组长度while (left right) {//[1,1),这里这样写区间就错了所以是leftrightint mid left ((right - left) 1);//相当于mid(leftright)/2,防止溢出if (nums[mid] target)//找到就返回下标return mid;else if (nums[mid] target)//目标在右边改变左区间,需要保持区间左闭右开和while循环一致left mid 1 ;//因为要与区间保持一致左边是闭的需要加一else if (nums[mid] target)right mid;//右边是开的不用加一}return -1;}
}27. 移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数但输出的答案是数组呢?
请注意输入数组是以**「引用」**方式传递的这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说不对实参作任何拷贝
int len removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i 0; i len; i) {print(nums[i]);
}示例 1
输入nums [3,2,2,3], val 3
输出2, nums [2,2]
解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。示例 2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,4,0,3]
解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示
0 nums.length 1000 nums[i] 500 val 100
文章讲解https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解https://www.bilibili.com/video/BV12A4y1Z7LP
方法一暴力破解
思路
两层for循环第一个for遍历数组中的元素如果当前元素是要删除的则将之后的元素全都往前移动一位。
复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {public int removeElement(int[] nums, int val) {int len nums.length;for (int i 0; i len; i) {if (nums[i]val){// 找到要删除的元素for (int j i1; j len; j) {nums[j-1]nums[j];// 元素左移一位}i--;// 因为下标i以后的数值都向前移动了一位所以i也向前移动一位len--;}}return len;}public static void main(String[] args) {int[] nums{-1,0,3,3,9,12};Solution s1 new Solution();System.out.println(s1.removeElement(nums,3));}
}方法二双指针
思路
定义两个指针slow是指向需要输出的结果fast是遍历输入数组用的。
首先先看fastfast找要删除的元素找不到的话就将fast所在元素赋值给slow所在元素两指针都往后移一个找到的话就只将fast往后移slow也就是结果不需要添加。直到fast遍历完整个数组也就是fastnums.length的时候终止循环。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {public int removeElement(int[] nums, int val) {int slow0;for(int fast0;fastnums.length;fast){if(nums[fast]!val){nums[slow]nums[fast];slow;}}return slow;}
}根据代码来的图
