計算Leetcode的時間複雜度及空間複雜度

1. Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in  range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[j] == target - nums[i]:
                    return[i,j]
  • 時間複雜度為O(n2) (兩個for迴圈，每個for迴圈執行n次，所以是n2)
  • 空間複雜度：O(1)，沒有使用到陣列去存取到data。

169. Majority Element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        # The majority element is the element that appears more than ⌊n / 2⌋   so
        # of  majority Element > n/2
        # of not majority Element < n/2
        # (of  majority Element) -(of not majority Element) > 0
        #         a              -         b                >  0
        index, count = 0 , 1          
        for i in  range(1, len(nums)):  
            if nums[index] == nums[i]:    
                count += 1
            else:
                count -=1       
                if count== 0:
                    index = i 
                    count = 1  
        return nums[index]
  • 時間複雜度為O(n)( 一個for迴圈，for迴圈執行n次)
  • 空間複雜度：O(1)，沒有使用到陣列去存取到data。

217. Contains Duplicate

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False
  • 時間複雜度為O(nlogn) ( 一開始nums.sort()先進行排序，大部分的sort都皆為O(nlogn)，接下來雖然有一個for迴圈，但是省略常數項所以最終還是O(nlogn)
  • 空間複雜度：O(1)，沒有使用到陣列去存取到data。

35. Search Insert Position

class Solution(object):
    def searchInsert(self, nums, target):
        
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        if (target > nums[len(nums) -1 ]):
            return len(nums)
        for i in range(len(nums)):
            if nums[i] >=target:
                return i
  • 時間複雜度為O(n) ( 一個for迴圈，for迴圈執行n次)
  • 空間複雜度：O(1)，沒有使用到陣列去存取到data。

243. Shortest Word Distance

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
          dist = float("inf") #無限大   　
          i , index1,index2 = 0, None,None
          while i <len(wordsDict):
                if wordsDict[i] == word1:
                    index1 =i
                elif wordsDict[i] == word2:
                    index2 =i
                
                if index1 != None  and index2 !=None:
                    dist = min(dist,abs(index1 - index2))  #绝對值 # 比較新的dist舊的dist哪個小)
                    
                i += 1
                
          return dist
  • 時間複雜度為O(n) ( 一個while，每執行一次while只有一個索引會更新，最多就執行n次)
  • 空間複雜度：O(1)，沒有使用到陣列去存取到data。

118. Pascal’s Triangle

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:

        result =[]
        for i in range(numRows):
            result.append([])
            for j in range(i+1):
                if j in (0,i):
                    result[i].append(1)
                else:
                    result[i].append(result[i-1][j-1]+result[i-1][j])
        return result
  • 時間複雜度為O(numRows2) ( 這邊的n是numRows，for迴圈內包for迴圈，所以是 numRows2)
  • 空間複雜度： O(numRows2) ，這邊有一個 result =[ ]存取data，第一行一個元素，第二行有兩個元素，一直加到最後一行numRows都是需要被存到result =[ ]中的data，以三角形公式(上底+下底)*高除二來得知numRows*(numRows+1)/2，固可簡化為O(numRows2) 。