526互联

Day1

发布时间 2023-07-27 23:00:53作者: 大蟒蛇进动吐痰

 

二分查找基本概念和原理：有一个有序的列表，比较一个元素与数组中的中间位置的元素大小。如果比中间位置的元素大，则继续在后半部分的数组中进行二分查找。如果比中间的位置小，则在数组的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数组长度都是之前数组的一半，一直到找到相等元素的位置或者没有找到要找的元素。

 

leetcode 704:

def binary_search (nums, target) :
    left = 0 
    right = len(nums) - 1 
    while(left <= right) :
        mid = left + (right-left)//2 
        if (nums[mid] < target) :
            left = mid + 1 
        elif (nums[mid] == target):
            return mid 
        elif (nums[mid] > target) :
            right = mid - 1 
    
    return -1

关于其中 mid = left + (right - left) // 2 而不是直接的 mid = (right + left) / 2， 因为可能第二种写法，l+r 可能会大于INT_MAX 而导致数组溢出问题。 

相关学习链接：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E8%AF%A6%E8%A7%A3.md

https://www.zhihu.com/question/36132386/answer/530313852

移除元素：

leetcode: 27

暴力解法：

def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        size = len(nums) 
        i = 0
        while i < size :
            if nums[i] == val :
                for j in range(i+1, size) :
                    nums[j-1] = nums[j] #平移数组剩余元素，覆盖当前需要删除的元素
                #for k in nums:
                    #print(k, end="")
                #print('\n')
                size -= 1 
                i -= 1 
            i += 1 #如果不相等，继续遍历下一个元素
        return size

第一层循环用来遍历数组，第二层循环用来更新数组。第一层使用for循环，无法更新i的值。即使for循环内改变i值，也无法影响循环定义的i的值继续。

nums[j-1] = nums[j] 此时nums[j-1] 就是需要删除的元素的值，使用下一个元素的值来覆盖当前值，达到删除的效果。

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

快：寻找新数组（不含有目标元素的数组）的元素

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

相关阅读：https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%8F%8C%E6%8C%87%E9%92%88%E6%8A%80%E5%B7%A7.md

也就是说，fast 遇到目标值就直接跳过，否则就赋值给slow指针，并让slow前进一步。

def removeElement(nums, val) :
    fast = 0
    slow = 0 
    size = len(nums) 
    while fast < size :
        #快指针将会跳过val
        if nums[fast] != val : 
            nums[slow] = nums[fast] 
            slow+=1 
        fast += 1 
    
    return slow

举例理解快慢指针，有数组 nums = [1, 1, 2, 3, 4, 5, 5, 6], val = 4 在这个时候fast 和 slow的初始值都是 0 也就是数组中的 1 

当 nums[fast] 不等于 val的时候，nums[slow] 随之更新，确保 nums[0, slow-1] 是不包含值为val的元素。 当fast 索引到目标值 4 的时候 num[fast] = 4, 此时的slow不更新。也就是说 when fast = 5, slow = 4，此时num[fast] 不等于 val, 开始进入if 条件，准备更新slow 和 nums[slow]的值。nums[slow] = nums[fast] -> nums[4] = nums[5], 用nums[5]的值去覆盖之前等同于val的nums[4]的值。