代码随想录训练营第一天|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
    

    全部评论

    相关推荐

    lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
    点赞 评论 收藏
    分享
    评论
    1
    收藏
    分享

    创作者周榜

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