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
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