Day01——数组专题

梦里梦外; 2024-04-03 10:29 109阅读 0赞

#### 文章目录 ####

*   *   *  1.二分查找：
         *  2.移除元素：
         *   *  双指针法
         *  3.有序数组的平方：
         *   *  双指针法:

--------------------

#### 1.二分查找： ####

补充：

*  **数组下标都是从0开始的。**
 *  **数组内存空间的地址是连续的**

正是**因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。**

**查找目标值target，返回该值的数组元素的下标。**

二分法适用于已经排好序的数组，定义两个变量，一个left,一个right,则mid = left + ((right - left) >> 1)

**1.针对左闭右闭算法** \[left,right\]

如果 target==arr\[mid\],中间值正好等于要查找的值，则返回下标，return mid;

如果 target<arr\[mid\],要找的值小于中间的值，则再往数组的小端找，**right=mid-1**;

如果 target>arr\[mid\],要找的值大于中间的值，则再往数组的大端找，left=mid+1;

**注意:**

while(right >= left)
    
    int right = nums.length - 1;

**2.针对左闭右开算法** \[left, right）

如果 target==arr\[mid\],中间值正好等于要查找的值，则返回下标，return mid;

如果 target<arr\[mid\],要找的值小于中间的值，则再往数组的小端找，**right=mid**;

如果 target>arr\[mid\],要找的值大于中间的值，则再往数组的大端找，left=mid+1;

**注意：**

while(right > left)
    
    int right = nums.length;

#### 2.移除元素： ####

##### 双指针法 #####

双指针法（快慢指针法）： **通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**

定义快慢指针

*  快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组(目标元素就是要移除的元素)
 *  慢指针：指向更新之后新数组下标的位置

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

#### 3.有序数组的平方： ####

##### 双指针法: #####

数组是有序的， 但是负数平方之后可能成为最大数,那么数组平方的最大值就在数组的两端，不是最左边就是最右边。

此时可以考虑双指针法了，left指向起始位置，right指向终止位置。

定义一个新数组result，和原来A数组一样的大小，让index指向result数组终止位置。

如果`A[left] * A[left] < A[right] * A[right]` 那么`result[index--] = A[right] * A[right]; right--;`

如果`A[left] * A[left] >= A[right] * A[right]` 那么`result[k--] = A[left] * A[left]; left++;`

public int[] sortedSquares(int[] nums) {
        
            int right = nums.length - 1;
            int left = 0;
            int[] result = new int[nums.length];
            int index = nums.length - 1;
            while (right <= left){
        
                if(nums[right] * nums[right] > nums[left] * nums[left]){
        
                    result[index--] = nums[right] * nums[right];
                    right--;
                }
                else {
        
                    result[index--] = nums[left] * nums[left];
                    left++;
                }
            }
            return result;
        }