Python力扣刷题01-二分查找&移除元素

ゞ浴缸里的玫瑰 2023-09-28 23:19 33阅读 0赞

### 二分查找 ###

「二分查找算法（Binary Search Algorithm）」：也叫做 「折半查找算法」、「对数查找算法」。是一种在有序数组中查找某一特定元素的搜索算法。

基本算法思想：先确定待查找元素所在的区间范围，在逐步缩小范围，直到找到元素或找不到该元素为止。

二分查找算法的过程如下所示：

每次查找时从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；  
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。  
如果在某一步骤数组为空，则代表找不到。

#### 704.二分查找 ####

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

题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

案例：

示例 1:
    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4
    
    示例 2:
    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

实现：

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

#### 27.移除元素 ####

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

题目描述：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

案例：

输入：nums = [3,2,2,3], val = 3
    输出：2, nums = [2,2]
    解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

方法一:暴力解法

class func():
        def func01(self, nums, val):
            n = len(nums)
            count = 0
            i = 0
            while (i<n-count):
                if nums[i] == val:
                    for j in range(i+1,n):
                        nums[j-1] = nums[j]
                    count += 1
                else:
                    i += 1
            return n-count

方法二:双指针法

class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            fast_index = 0
            slow_index = 0
            while fast_index < len(nums):
                if nums[fast_index] != val:
                    nums[slow_index] = nums[fast_index]
                    slow_index += 1
                fast_index += 1
            return slow_index