算法训练营Day1>>704、二分查找+27、移除元素+977、有序数组的平方

犹豫了好久，观望了好久，今天下定决心要开始了。虽然工作很忙，但不怕，我的动力也很足。

代码随想录算法训练营-数组-二分查找

*****************

虽然这是一道简单题，但是太久没有手撕过算法题了，思路很清晰，但写起来磕磕绊绊的，有种汉译英时写中式英语的感觉

思路应该很明确：

1. 把特殊情况排除了，那就是target小于第一个元素、大于最后一个元素的情况；
2. 定义两个指针用于执行二分法；
3. 二分法的核心实现
1. 首先根据数组的实际情况来写while循环的判断条件，如果数组是左闭右闭的，那么left==right是可以取到对应的数值的，所以while循环的条件应该是left<=right；
2. 其次根据左右计算出middle的值；
3. 最后再根据target与middle对应的值做对比，如果相等，则直接返回middle；如果target大，则更新左指针；否则，更新右指针；这里尤其要注意更新左右指针的方式，因为已经确定middle对应的值不等于target，所以下次就不要再找这个值了，而且是左闭右闭的数组，下次寻找还是会看左右边界的值，所以应该是right=middle-1/left=middle+1。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (nums[0] > target || nums[right] < target) {
            return -1;
        }
      // 刚开始考虑边界特殊情况时，在想如果刚好左右边界值等于target，那岂不是直接返回左右指针就行了，就不用再去执行二分查找了，但是实际上好像有没有这两个判断并没啥区别，消耗内存和执行时间上都没啥差异。
	  if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

****************

看到这个题目的第一想法竟然是先给数组排个序，然后直接返回val的坐标减2就可以了。但是给数组排序如果遇到一个刚好是降序的数组，val又是最大值，那这个时间复杂度应该就会很高，可能会过不了，时间原因就先不试了。

看了暴力解法，理解其大概思路就是直接遍历整个数组，找到val后，就让后面的元素更新上来，同时记录数组长度减1，这样遍历完整个数组后，就可以得到移除元素后的数组长度了。

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < n; j++){
                    nums[j-1] = nums[j];
                }
                i--;
                n--;
            }
        }
        return n;
    }
}

也看了双指针的解法，时间原因就简单理解了下思路，等周末再补具体的代码实现了。

********************

看到题目第一反应就是平方后排序，暴力解法

大致理解了下双指针解法的思路：

1. 定义两个指针，分别记录首尾元素，用于后续分别平方比较大小
2. 定义一个新的数组，用于存放平方后的元素
3. 核心逻辑实现
1. 比较左右指针对应数组元素平方后的大小
2. 如果左边的大，就把左边平方后的值放到新数组的最后；反之，同理

刚开始有点没太理解这句代码result[index--] = nums[left] * nums[left]，就觉得index本身就已经是result.length-1了，为什么赋值的时候还要减1，后面想了下这个运算的逻辑，应该是先赋值，再去做减1的运算吧。

明天还要上班，本牛马要休息了今天就先到这儿了，打个卡，27和977欠下的周末来还