代码随想录算法训练营第一天｜LeetCode704.二分查找、LeetCode27.移除元素

作者：小桥流水78 | 2024-08-10 16:22:17

踩

704.二分查找

文章讲解：代码随想录

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

思路：题目的前提是数组为有序数组，且数组中无重复元素。因为一旦有重复元素，通过二分查找法返回的元素下标就不是唯一的。二分查找又叫折半查找，就是通过对数组不断的折半来确定目标值是在前半部分或后半部分，减少了查找时间。

左闭右闭：拿到题目后，因为前段时间刚刚自学完二分查找，所以拿到题目以后也算得心应手，十分钟就写完了代码，在测试的时候报错，发现是自己没有编写没找到目标值的返回方式，添加以后，测试用例完全正确。下面附上我的代码：


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:
                right = mid - 1
            elif nums[mid] == target:
                return mid
            else:
                left = mid + 1
        else:
            return -1

左闭右开：看到训练营的提示说二分查找有两种方法：左闭右开和左闭右闭。但是我不清楚自己写的是哪种方法，查看文章讲解后，对两种方法有了清晰的认识。下面附上另一种方法（左闭右开）：


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:
                right = mid # 还有这里的差别
            elif nums[mid] == target:
                return mid
            else:
                left = mid + 1
        else:
            return -1

两种方法的时间复杂度均为O(logn)。

27.移除元素

文章讲解：代码随想录

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

思路：由于数组中元素的内存地址是连续的，删除后还需要将其他元素往前移动填补空缺。

暴力解法：拿到题目以后第一个想到的就是两层循环，但是自己写出来的一直报错也没找到问题所在，查看了文章讲解，最终的代码如下：


class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i, size = 0, len(nums)
        while i < size:   #当循环遍历的次数小于数组的长度时
            if nums[i] == val:  # 如果找到了要删除的目标数在i位置
                for j in range(i+1,size): # 将其删除，其后的数都往前移动一位
                    nums[j - 1] = nums[j]
                i -= 1 # 移动后i应该也往前一位
                size -= 1  #数组长度也减少一个
            i += 1  #没找到的话，i往后一位继续找
        return size  #最后返回剩下的数组长度

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

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组

慢指针：指向更新新数组下标的位置


class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        fast = 0 # 收集等于目标值的值
        slow = 0 # 收集剩下的值
        size = len(nums)
        while fast < size:  # 如果等于nums[fast]会越界
            if nums[fast] != val:   # 如果fast指的值不是目标值
                nums[slow] = nums[fast].    # 就把该值与slow替换
                slow += 1  #slow会增加一
            fast += 1  # 如果fast指的值是目标值，就给fast增加一
        return slow  #最后slow收集了剩下的值的长度

暴力法的时间复杂度为O(n^2)，双指针法的时间复杂度为O(n)。

今日心得：

首先关于二分查找法，了解到了两种方法，对自己熟知的方法也有了更清晰的认识，要注意区间的开闭。

其次关于移除元素，也掌握到了两种解决办法，暴力法要明确好循环边界，以及注意由于数组的特性，需要将其余数组向前移动。双指针法要明确好快指针与慢指针所代表的意义，双指针法的时间复杂度更小。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/959313