【leetcode】第一章数组

704. 二分查找

• 边界值需注意
• left代表左边界下标值，right代表右边界的下标值
• 当数组只有一个元素时，此时如果找到该元素应该返回下标0，因此条件为left<=right
• 当mid的元素值大于target时，此时说明我们想找的target在右边，因此需要改变右边界的值，right=mid-1。当mid的元素小于target同理。

public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;int mid;while (left <= right) {mid = left + (right-left)/2;if (nums[mid] == target) {return mid;}else if (nums[mid] > target) {right = mid - 1;}else {left = mid + 1;}}return -1;}

27. 移除元素

1. 暴力解法

public int removeElement(int[] nums, int val) {// 暴力解法int size = nums.length;for (int i = 0; i < size; i++) {// 若遇到val元素，则更新数组if (nums[i] == val) {for (int j = i+1; j < size; j++) {nums[j-1] = nums[j];System.out.println("size:"+size);}size--;i--; // 由于整体向前移动了一位，因此该位的值需要进行判断，所以需要保持不动}}return size;}

2. 双指针方法

• 定义一个left指针，一个right指针，left指向需要移除的元素，right指针用来跳过val元素，不断来更新新的元素数组。
• 只要nums[right]不为val，则更新left指针的元素值，并同时递增两个索引。重复这一过程，直到right到达数组末尾。left为移除元素后的数组长度。

public int removeElement(int[] nums, int val) {int left = 0;for (int right = 0; right < nums.length; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}

3. 双指针优化方法

• 当删除的元素很少的时候（假设该数组只有第一个元素需要删除），此时使用第一种方法，假设n为数组元素的数量，则赋值操作需要进行n-1次，因此需要进行优化。
• 当需要删除元素很少时（假设该数组只有第一个元素需要删除），我们只需要交换第一个元素和最后一个元素的值即可。因此我们定义left指针指向第一个元素，right指针指向最后一个元素，若遇到要移除的元素时，便将left此处的值赋为right位置的值。

public static int removeElement(int[] nums, int val) {int left = 0;int right = nums.length - 1;int size = nums.length;while (left < size) {if (nums[left] == val) {nums[left] = nums[right];right--;size--;}else {left++;}}return size;}

参考链接

• 移除元素双指针方法