●day 1 第一章数组part01 （1.22）

第一题：704. 二分查找

一、基本原理

二分查找是一种在有序数组中查找目标元素的高效算法。它利用数组元素有序的特性，通过不断将查找范围减半，快速定位目标元素。

二、具体步骤

初始化查找范围：首先，确定初始的查找范围，将左边界设置为数组的第一个元素的索引（通常为 0），将右边界设置为数组的最后一个元素的索引（通常为数组长度减 1）。
计算中间元素：在每一次查找过程中，计算当前查找范围的中间元素的索引。通常使用 (left + right) / 2（或使用位运算 (left + right) >> 1）来计算，这样可以快速得到范围的中间位置。
比较中间元素和目标元素：将中间元素的值与目标元素的值进行比较。
调整查找范围：若中间元素的值大于目标元素：说明目标元素在左半部分，因此更新右边界为中间元素的索引（或中间元素索引减 1），将查找范围缩小到左半部分。若中间元素的值小于目标元素：说明目标元素在右半部分，因此更新左边界为中间元素的索引加 1，将查找范围缩小到右半部分。若中间元素的值等于目标元素：表示已经找到目标元素，返回中间元素的索引作为结果。
结束条件：

重复上述步骤，不断缩小查找范围，直到找到目标元素或左边界大于等于右边界。

若左边界大于等于右边界时还未找到目标元素，则说明目标元素不在数组中，返回 -1 作为结果。

通过这种不断将查找范围减半的方式，二分查找可以在 $O(log n)$ 的时间复杂度内找到目标元素，相比顺序查找的 $O(n)$ 时间复杂度，在处理大型有序数组时具有更高的效率。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 使用 left <= right 确保可以处理只有一个元素的情况
        while (left <= right) {
            int middle = (left + right) >> 1;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}

第二题：27.移除元素

一、整体思路

使用双指针法来解决移除元素的问题，通过一个快指针 fast 遍历数组，一个慢指针 slow 来标记最终结果中元素的位置。当快指针指向的元素不等于 val 时，将该元素复制到慢指针所指的位置，并将慢指针向前移动一位，最终慢指针的位置就是移除元素后数组的有效元素长度。

二、具体步骤

指针初始化：slow = 0：慢指针 slow 用于存储最终结果中元素的位置，初始化为 0，表示从数组的起始位置开始存储最终的结果元素。fast = 0：快指针 fast 用于遍历整个数组，初始化为 0。
遍历数组：使用 for(int fast = 0; fast < nums.length; fast++) 开始遍历数组。
元素判断与操作：对于 nums[fast]，检查它是否等于 val。若 nums[fast]!= val：说明该元素是需要保留的元素，将 nums[fast] 的值赋给 nums[slow]，即将该元素复制到慢指针所指的位置。然后将 slow 指针加 1，更新存储下一个有效元素的位置。若 nums[fast] == val：则不进行任何操作，直接让 fast 指针继续向前移动，相当于跳过该元素。
最终结果：当 fast 指针遍历完整个数组后，slow 指针所指的位置就是移除元素后数组的有效元素的长度，返回 slow 作为结果。

总结：代码通过双指针的方法，巧妙地实现了在原数组中移除指定元素的功能。快指针 fast 遍历数组，慢指针 slow 用于存储最终结果中元素的位置，只有当元素不等于 val 时，才将其存储到慢指针位置，避免了元素的移动操作，实现了 $O(n)$ 的时间复杂度。

例如，对于 nums = [3,2,2,3] 和 val = 3 的情况：

开始时，slow = 0，fast = 0，nums[fast] = 3 等于 val，fast 指针移动到下一个元素。
当 fast = 1 时，nums[fast] = 2 不等于 val，将 nums[fast] 赋值给 nums[slow]，即 nums[0] = 2，slow 变为 1。
当 fast = 2 时，nums[fast] = 2 不等于 val，将 nums[fast] 赋值给 nums[slow]，即 nums[1] = 2，slow 变为 2。
当 fast = 3 时，nums[fast] = 3 等于 val，fast 指针移动到下一个元素。
最终 slow = 2，表示移除元素后数组的有效元素长度为 2，且 nums = [2,2,_,_]。

这种方法避免了对数组元素的多次移动，只需要遍历一次数组，就能完成元素的移除和新数组的生成，提高了效率。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

第三题：977.有序数组的平方

一、整体思路

采用双指针法，利用原数组已按非递减顺序排序的特性，从数组的两端向中间遍历，比较两端元素平方的大小，将较大的平方值依次放入结果数组的末尾，从而实现最终结果数组按非递减顺序存储每个数字的平方。

二、具体步骤

初始化：k = nums.length - 1：定义 k 作为结果数组 result 的索引，从结果数组的末尾开始存储元素，因为我们要从大到小存储元素的平方。int[] result = new int[nums.length]：创建一个与原数组 nums 长度相同的结果数组，用于存储每个元素平方后并排序的结果。i = 0 和 j = nums.length - 1：定义两个指针，i 从数组 nums 的起始位置开始，j 从数组 nums 的末尾位置开始。
双指针遍历：使用 for(int i = 0, j = nums.length - 1; i <= j; ) 进行遍历。在每次迭代中，比较 nums[i] * nums[i] 和 nums[j] * nums[j] 的大小。
元素处理：若 nums[i] * nums[i] > nums[j] * nums[j]：说明 nums[i] 的平方值较大，将 nums[i] * nums[i] 存储到结果数组 result[k] 中。然后将 k 减 1，更新结果数组存储下一个元素的位置。将 i 加 1，使 i 指针向数组中间移动。若 nums[i] * nums[i] <= nums[j] * nums[j]：说明 nums[j] 的平方值较大或相等，将 nums[j] * nums[j] 存储到结果数组 result[k] 中。然后将 k 减 1，更新结果数组存储下一个元素的位置。将 j 减 1，使 j 指针向数组中间移动。
最终结果：当 i > j 时，遍历结束，结果数组 result 存储了原数组 nums 中每个元素平方后并按非递减顺序排列的元素，返回 result 数组。

总结：这种双指针方法利用了原数组的有序性，避免了先平方再排序的 $O(nlogn)$ 时间复杂度。通过从数组两端向中间比较元素平方的大小，将较大的平方值依次放入结果数组的末尾，只需要一次遍历就能完成操作，实现了 $O(n)$ 的时间复杂度。

例如，对于 nums = [-4, -1, 0, 3, 10]：

开始时，i = 0，j = 4，nums[i] * nums[i] = 16，nums[j] * nums[j] = 100，nums[j] * nums[j] 大，将 100 存储到 result[4]，k = 3，j = 3。
继续比较，nums[i] * nums[i] = 16，nums[j] * nums[j] = 9，nums[i] * nums[i] 大，将 16 存储到 result[3]，k = 2，i = 1。
继续比较，nums[i] * nums[i] = 1，nums[j] * nums[j] = 9，nums[j] * nums[j] 大，将 9 存储到 result[2]，k = 1，j = 2。
继续比较，nums[i] * nums[i] = 1，nums[j] * nums[j] = 0，nums[i] * nums[i] 大，将 1 存储到 result[1]，k = 0，i = 2。
最后，将 0 存储到 result[0]，得到结果数组 [0, 1, 9, 16, 100]。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int k = nums.length - 1;
        int[] result = new int[nums.length];
        for(int i = 0,j = nums.length-1; i <= j; ){
            if(nums[i]*nums[i] > nums[j]*nums[j]){
                result[k] = nums[i]*nums[i];
                k--;
                i++;
            }else{//包含小于和等于两种情况
                result[k] = nums[j]*nums[j];
                k--;
                j--;
            }
        }
        return result;

        
    }
}

#数组声明##刷题#