704. 二分查找、27. 移除元素
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]之间。
思路：
二分法对数据元素遍历，二分法需要注意target元素所在区间。
目标元素区间左闭右闭
时间复杂度：O(log n)
空间复杂度：O(1)
// 二分查找，区间【left,right】
public static void binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 数组的最后一个元素，闭区间
if (target < nums[0] || target > nums[right]) {
System.out.println(-1);
}
// 边界条件 left <= right
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
System.out.println(mid);
break;
} else if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid - 1;
}
}
if (left > right) {
System.out.println(-1);
}
}目标元素区间左闭右开
时间复杂度：O(log n)
空间复杂度：O(1)
// 二分查找，区间【left,right)
public static void binarySearch1(int[] nums, int target) {
int left = 0;
int right = nums.length; // 数组最后一个元素 +1 相当于开区间
if (target < nums[0] || target > nums[right]) {
System.out.println(-1);
}
// 边界条件 left < right
while (left < right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
System.out.println(mid);
break;
} else if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid;
}
}
if (left >= right) {
System.out.println(-1);
}
}问题：
获取mid值 不可使用int mid = (left + right) / 2 如果left 和 right的值过大，两数之和相加可能超出Int类型的最大限制，导致整数溢出，结果不准确。 可以使用 int mid = left + (right-left)/2 或者 int mid = left + ((right-left) >>1)
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
相向双指针思路：
定义双指针，一个从头遍历，一个从尾部遍历.
头部的元素如果是target，那么跟尾部互换位置。
尾部的元素如果是target，那么指针向前移动，直至指针指向元素不等于target.
代码如下：
/**
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
// 定义双指针，一个从头遍历，一个从尾部遍历
private static int removeElements(int[] nums, int val) {
int quick = nums.length - 1;
int slow = 0;
if (nums.length == 0) {
return 0;
}
// 数组最后一个元素是target情况
while (quick >= 0 && nums[quick] == val) {
quick--;
}
while (slow < quick) {
if (nums[slow] == val) {
// 交换元素位置
int temp = nums[slow];
nums[slow] = nums[quick];
nums[quick] = temp;
quick--;
}
slow++;
while (quick >= 0 && nums[quick] == val) {
quick--;
}
}
return quick + 1;
}问题
数组最后一个元素是target情况,quick会不断往前移动元素，如果数组的全部元素都为target， quick 为 -1.此时while循环先判断Num[quick]，那么会有数组越界问题。
while (nums[quick] == val && quick >= 0) {
quick--;
}异常信息
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at algorithm.removeElements.removeElements(removeElements.java:27)
at algorithm.removeElements.main(removeElements.java:15)所以需要先判断quick >= 0.即
while (quick >= 0 && nums[quick] == val) {
quick--;
}快慢指针法思路
定义快慢指针。同时从数组起点遍历元素。
快指针模拟双层for循环的第一层遍历，走遍所有数据元素，快指针指向的元素如果不是目标元素，就赋值给慢指针元素，将非目标元素全部移动到前面
慢指针所在位置就是非目标元素数量
代码如下
private static int removeElements2(int[] nums, int val) {
int quick = 0;
int slow = 0;
if (nums.length == 0) {
return 0;
}
for(quick = 0;quick < nums.length ;quick++){
if(nums[quick] != val){
nums[slow++] = nums[quick];
}
}
return slow;
}暴力解法思路
对数组进行排序，排序后遍历找到合适的size
代码如下
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
private static int removeElements1(int[] nums, int val) {
int size = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == val && nums[j] != val) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
}
}
for(int i = 0; i< nums.length;i++){
if(nums[i]==val){
break;
}
size ++;
}
return size;
}问题
排序后遍历找到合适的size总有问题。没有考虑特殊情况 一开始的写法,本意是数组已经排好序，只要找到第一个val，那么val所在下表就是数组的长度。
for(int i = 0; i< nums.length;i++){
if(nums[i]==val){
size = i;
break;
}
}但是如果数组只有一个元素2，而val等于3，那么size就会为默认值0,应该输出1才对，所以需要一个元素一个元素的去遍历，遍历的元素不等于val，那么size++.
for(int i = 0; i< nums.length;i++){
if(nums[i]==val){
break;
}
size ++;
}