代码随想录算法训练营第1天 | 704.二分查找、27.去除元素

704 二分查找

题目链接：704二分查找
解题思路：

1. 定义搜索区间【left, right】
2. left=0， right=len(nums) - 1
3. 查询到返回mid，未查询到返回-1。

代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0 
        right = len(nums) 
        while left < right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                right -= 1
            if nums[mid] < target:
                left +=  1
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0 
        right = len(nums) -1 
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                right -= 1
            if nums[mid] < target:
                left +=  1
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

27 去除元素

题目链接：27去除元素
解题思路：

1. 数据内存空间地址是连续的，不要使用额外的数组空间，删除其实就是覆盖。
2. fast 指针遇到val的元素跳过，将fast指针的元素赋值给slow指针，因此可以达到覆盖slow指针指向val值的内容。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        slow = 0
        fast = 0
        while fast < len(nums):
            if  nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        int fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            } 
            fast++;
        }
        return slow;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16