代码随想录训练营第一天|704. 二分查找|27. 移除元素

二分查找

二分查找前提:1. 有序 2. 无重复

  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)

如何判断最好自己举个例子手推一下,也不麻烦,但是想一下或者背一下也行。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while(left<=right):
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        
        return -1
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)

        while(left < right):
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        
        return -1

移除元素

有两种方法:

暴力法

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            i, l = 0, len(nums)
            while i < l:
                if nums[i] == val: # 找到等于目标值的节点
                    for j in range(i+1, l): # 移除该元素,并将后面元素向前平移
                        nums[j - 1] = nums[j]
                    l -= 1
                    i -= 1
                i += 1
            return l
    

    快慢指针

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)
    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            slow, fast = 0, 0
            while fast < len(nums):
                if nums[fast] != val:
                    nums[slow] = nums[fast]
                    slow += 1
                fast += 1
            return slow
    

    全部评论

    相关推荐

    nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
    点赞 评论 收藏
    分享
    门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
    你的秋招第一场笔试是哪家
    点赞 评论 收藏
    分享
    不愿透露姓名的神秘牛友
    07-10 12:05
    点赞 评论 收藏
    分享
    评论
    1
    收藏
    分享

    创作者周榜

    更多
    牛客网
    牛客网在线编程
    牛客网题解
    牛客企业服务