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

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

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

最后

以上就是痴情小天鹅为你收集整理的leetcode 704 & 75704: 二分查找75:颜色分类的全部内容，希望文章能够帮你解决leetcode 704 & 75704: 二分查找75:颜色分类所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。