代码随想录训练营｜Day 1｜数组理论基础，704. 二分查找，27. 移除元素

标签：target nums 704 元素 随想录 mid int 数组 移除

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

• start with index 0
• 数组内存空间的地址是连续的
• 数组的元素是不能删的，只能覆盖。

二维数组：

Binary Search

通过不断缩小搜索区间的范围，直到找到目标元素或者没有找到目标元素。

每一轮排除掉一定不存在目标元素的区间，在剩下 可能 存在目标元素的区间里继续查找。每一次我们通过一些判断和操作，使得问题的规模逐渐减少。

Example: 猜价格、翻字典etc

应用范围：

1. 在有序数组中进行查找一个数

   Array: 具有随机访问的特性

     在内存中连续存放，可通过index快速访问
   

   有序：可以通过当前元素附近的值推测出当前元素一侧的所有元素特性

2. Find the target in the array

两种思路：

1. 在循环体中查找元素
2. 在循环体中排除目标元素一定不存在的区间

A. Classic Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.
Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 104
• 104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

Solution:

先看位于数组中间的那个元素的值，如果中间元素=目标，返回index

否则在中间元素的左边或者右边继续查找

int mid = left + (right - left) / 2;
// 防止int overflow

Case 1: if target < array[mid], target exists in [L, mid - 1]

right index = mid - 1

Case 2: if target > array[mid], target exists in [mid + 1, R]

left index = mid + 1

Case 3: target == array[mid], return mid

Loop: L ≤ R, stops when L > R, 只有一个元素依旧进行，所以target cannot be ruled out

Not found: return -1

Corner Cases: array == null || array.length == 0

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

Time complexity: O(log N)

Space complexity: O(1)

编码要点

• 循环终止条件写成：while (left < right) ，表示退出循环的时候只剩下一个元素；
• 在循环体内考虑如何缩减待搜索区间，也可以认为是在待搜索区间里排除一定不存在目标元素的区间；
• 根据中间数被分到左边和右边区间，来调整取中间数的行为；
• 如何缩小待搜索区间，一个有效的办法是：从 nums[mid] 满足什么条件的时候一定不是目标元素去考虑，进而考虑 mid 的左边元素和右边元素哪一边可能存在目标元素。

一个结论是：当看到 left = mid 的时候，取中间数需要上取整，这一点是为了避免死循环；

• 退出循环的时候，根据题意看是否需要单独判断最后剩下的那个数是不是目标元素。

边界设置的两种写法：

• right = mid 和 left = mid + 1 和 int mid = left + (right - left) / 2;

  一定是配对出现的；

• right = mid - 1 和 left = mid 和 int mid = left + (right - left + 1) / 2;

  一定是配对出现的。

For Future References

题目链接：https://leetcode.cn/problems/binary-search/

文章讲解：https://programmercarl.com/0704.二分查找.html

视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

Related Leetcode #: 704；374；35；34；153；154；33；81；278；852；1095；4；69；287；1300；875；410；1011；1482

Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

暴力解法

两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

class Solution {
    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;
    }
}

Time Complexity：O(n^2)
Space Complexity：O(1)

Two Pointers

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针:

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

class Solution {
    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];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

Time Complexity：O(n)
Space Complexity：O(1)

For Future References

题目链接：https://leetcode.cn/problems/remove-element/

文章讲解：https://programmercarl.com/0027.移除元素.html

视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

标签：target,nums,704,元素,随想录,mid,int,数组,移除
From： https://www.cnblogs.com/bluesociety/p/16717792.html