一、數(shù)組理論基礎(chǔ)

  • 數(shù)組下標都是從0開始的
  • 數(shù)組內(nèi)存空間的地址是連續(xù)的
  • 數(shù)組的元素是不能刪的，只能覆蓋

二、刷題

第一題 704.二分查找

題目鏈接：https://leetcode.com/problems/binary-search/

難度：easy

思路：

題干sorted ascending array ，再加上給一個target返回符合的索引，很顯然是需要縮小查找范圍——首選二分查找法

再看限制條件，nums長度，時間復雜度最多為O(n^2), 如果用二分查找時間復雜度是O(logn) 符合題目條件

代碼：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # sorted array - BS 目的：縮小查找范圍
        # l, r
        l=0
        r=len(nums)
        while l<r:
            m = l + (r - l)//2
            if nums[m] == target:
                return m
            elif nums[m]>target:
                r = m
            else:
                l = m+1
        return -1

習慣寫左閉右開的方法，l<r, 其中r是不可能被遍歷到的位置。

時間復雜度：O（logn)

空間復雜度：O（1）

第二題 34.有序數(shù)組找首位末位

題目鏈接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

難度：medium

思路：

non-decreasing order-BS，target

又要求O(log n) ----二分查找

這道題的難點在于：如何確定下邊界和上邊界，怎么縮小范圍，初刷沒做出來，看答案看懂的。

代碼：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        #non-decreasing order-BS，target，lower bound & upper bound
        #O(log n) ---- 100% BS solution
     
        ''''while l<r:
            if nums[m]>target:
                r=m
            if nums[m]<target:
                l=m+1
            if nums[m]==target:
                l+=1
                r-=1
                #這道題的難點在于：如何確定下邊界和上邊界，怎么縮小范圍
        return [-1,-1]'''
        def search(x):
            l, r = 0, len(nums)           
            while l < r:
                m = l+(r-l) // 2
                if nums[m] < x: #這里嚴格小于縮小范圍會得到下邊界，同理嚴格大于縮小范圍的思路會得到上邊界。很tricky的一個細節(jié)，要注意！
                    l = m+1
                else:
                    r = m                    
            return l
        
        l = search(target)
        r = search(target+1)-1
        
        if l <= r:
            return [l, r]
                
        return [-1, -1]
'''
[5,7,7,7,7,8,8,8,10] target=8
l=search(8)
r=search(9)-1
search(x)
l=0,5,
r=9,9,
m=4,7,
nums[m]=7<8
nums[m]=8
expect output[5,7]
'''

debug:　　IndentationError: unexpected indent  縮進不對

時間復雜度：O（logn）

空間復雜度：O（1）

第三題 35.搜索插入位置

題目鏈接：https://leetcode.com/problems/search-insert-position/

難度：easy

思路：

sorted array+target需要縮小范圍搜索，用二分查找

找下邊界的題，都是一個套路模版，和34題幾乎一樣

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l=0
        r=len(nums)
        while l<r:
            m=l+(r-l)//2
            if nums[m]<target:
                l=m+1else:
                r=m
        return l

時間復雜度：O（logn）

空間復雜度：O（1）

第四題 27.移除元素

題目鏈接：

https://leetcode.com/problems/remove-element/

難度：easy

思路：

要求對等于val的值被替換成其他的，剩下的不管。那就只用遍歷一遍，等于va的都跳過，不等于的值才可以按順序被替換進array，剩下的位置都是空

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p=0
        for i in range(len(nums)):
            if nums[i]==val:
                continue
            nums[p]=nums[i]
            p+=1
        return p

時間復雜度：O（n）

空間復雜度：O（1）

 

總結(jié)：

今天刷了4道題，704，34，35都是BS，27很簡單 算不上two pointers.

熟練掌握了二分查找尋找下邊界的模版

學習時長2小時，效果還不錯，再接再厲。