704: 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

75:颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

解法1

# 方法2:三路快排。假定索引-1都是小于1的，索引len(nums)都是大于1的，遍历中间的。有点像快排
class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        low = -1
        high = len(nums)
        i = 0
        while i < high:
            if nums[i] < 1:
                low += 1
                nums[low], nums[i] = nums[i], nums[low]
                i +=1
            elif nums[i] > 1:
                high -= 1
                nums[i], nums[high] = nums[high], nums[i]
            else:
                i += 1

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

解法2

# 方法1
class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        zero_num = 0
        one_num = 0
        two_num = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                zero_num += 1
            elif nums[i] == 1:
                one_num += 1
            else:
                two_num += 1
        for i in range(len(nums)):
            if i < zero_num:
                nums[i] = 0
            elif i < one_num + zero_num:
                nums[i] = 1
            else:
                nums[i] = 2

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: blog.csdn.net，作者：weixin_43178406，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_43178406/article/details/86652007