代码随想录算法训练营第一天|704.二分查找、27.移除元素

wuyijia / 2023-05-10 / 原文

704-二分查找

讲解链接

【要点】

1.使用二分法的前提：数组要有序，且无重复元素

2.算法复杂度：

时间复杂度：O(log n)
空间复杂度：O(1)

【注意】

1.在二分法后续处理中可能会导致middle的范围超过 int 的数据范围。见如下，

1 int middle = left + ((right - left) / 2);// 防止溢出等同于(left + right)/2 算数计算顺序不同

2.在Python中/表示浮点整除法，返回浮点结果，也就是结果为浮点数; 而//在Python中表示整数除法，返回大于结果的一个最大的整数，意思就是除法结果向下取整。

【代码实现】

 1 class Solution(object):
 2     def search(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: int
 7         """
 8         # 避免当 target 小于nums[0] 大于nums[len(nums) - 1]时多次循环运算
 9         if(target < nums[0] or target > nums[len(nums) - 1]):  
10             return -1
11         left = 0
12         right = len(nums) - 1
13 
14         while left <= right: #区间为[] ,影响的是不是取等
15             mid  = left + (right - left) // 2  #向下取整
16 
17             if nums[mid] == target:
18                 return mid
19             elif nums[mid] > target:
20                 right = mid - 1 
21             else:
22                 left = mid + 1
23         return -1

 1 class Solution(object):
 2     def search(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: int
 7         """
 8         # 避免当 target 小于nums[0] 大于nums[len(nums) - 1]时多次循环运算
 9         if(target < nums[0] or target > nums[len(nums)]):  
10             return -1
11         left = 0
12         right = len(nums)
13 
14         while left < right: #区间为[) ,不取等号
15             mid  = left + (right - left) // 2  #向下取整
16 
17             if nums[mid] == target:
18                 return mid
19             elif nums[mid] > target:
20                 right = mid 
21             else:
22                 left = mid + 1
23         return -1

27-移除元素 :使用双指针法（快慢指针法）

【注意】

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

【代码】

暴力解法：两层for循环，时间复杂度为O(n^2)

 1 class Solution(object):
 2     def removeElement(self, nums, val):
 3         """
 4         :type nums: List[int]
 5         :type val: int
 6         :rtype: int
 7         """
 8         size = len(nums)
 9 
10         for i in range(size):
11             if(nums[i] == val):
12                 for j in range(i+1,size):
13                     nums[j - 1] = nums[j]
14                 i = i -1
15                 size = size -1 
16 
17         return size
18

双指针：

 1 class Solution(object):
 2     def removeElement(self, nums, val):
 3         """
 4         :type nums: List[int]
 5         :type val: int
 6         :rtype: int
 7         """
 8         fast = 0 #快指针
 9         slow = 0 #慢指针
10         size = len(nums)
11 　　　　　
12         while fast < size: # 不加等于是因为，a = size 时，nums[a] 会越界
13             if nums[fast] != val:
14                 nums[slow] = nums[fast]
15                 slow += 1
16             fast += 1
17 
18         return slow