算法记录 | Day01（数组01）

• 704. 二分查找
• 27. 移除元素

704题：二分查找

【思路】
有序数组按升序排序，如何找到目标值？
时间复杂度 O(logN)，主要通过取中间点来节省遍历的次数，重点在于边界值的判断，找到合适的那一半数据空间。

class Solution {
    public int search(int[] nums, int target) {
        // 条件里已为升序，不再单独排序
        // 确认数组左右边界
        int left = 0;
        int right = nums.length - 1;

        // 此处结束循环判断使用下标
        while(left <= right){
            // 确认中间点，这边right-left 为防止数字过大时的溢出情况
            int mid =  (right - left) / 2 + left ;
            int num = nums[mid];
            if(num == target){
                return mid;
            } else if(target > num){
                // 目标值落在 右半段。移动筛选区间的左边界，减少一半选择范围
                left = mid + 1;
            } else {
                // 目标值落在 左半段。移动筛选区间的右边界至中间居左
                right = mid - 1;
            }
        }
        // 表示异常
        return -1;
    }
}

27. 移除元素

【题目】
给你一个数组nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

【思路】

1. 暴力解法（直接双重for 移除数组元素，但是时间复杂度为 O(n^2)）

 public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for(int i = 0; i < size; i++){
            if(nums[i] == val){  // 发现需要移除的元素，就将数组集体向前移动一位
                for(int j = i + 1; j < size; j++){
                    nums[j-1] = nums[j];
                }
                i--;  // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }

2. 快慢指针 （一个快指针和慢指针在一个for 循环内完成两个 for 循环的工作）
   本题中，右指针指向当前将要处理的元素，左指针指向下一个将要赋值的位置。

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