leetcode刷题(python)——(七)

01.03.10 练习题目（第 07 天）

1. 0075. 颜色分类

1.1 题目大意

描述：给定一个数组 $nums$，元素值只有 $0$、$1$、$2$，分别代表红色、白色、蓝色。

要求：将数组进行排序，使得红色在前，白色在中间，蓝色在最后。

说明：

• 要求不使用标准库函数，同时仅用常数空间，一趟扫描解决。
• $n==nums.length$。
• $1\le n\le 300$。
• $nums[i]$ 为 $0$、$1$ 或 $2$。

示例：

• 示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
1
2

• 示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]
1
2

解题思路

使用双指针法来解题，把数组中的0和2放置到两侧，当两个指针相等时停止循环

我的题解

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        head, tail = 0, len(nums)
        while(head != tail):
            if nums[head] == 0:
                nums.insert(0, nums.pop(head))
            elif nums[head] == 2:
                nums.insert(tail, nums.pop(head))
                tail -= 1
                continue
            head += 1
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 0215. 数组中的第K个最大元素

2.1 题目大意

描述：给定一个未排序的整数数组 $nums$ 和一个整数 $k$。

要求：返回数组中第 $k$ 个最大的元素。

说明：

• 要求使用时间复杂度为 $O(n)$ 的算法解决此问题。
• $1\le k\le nums.length\le 10^5$。
• $-10^4\le nums[i]\le 10^4$。

示例：

• 示例 1：

输入: [3,2,1,5,6,4], k = 2
输出: 5
1
2

• 示例 2：

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
1
2

解题思路

使用排序算法即可，这里使用快排

我的题解

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        pivot = random.choice(nums)
        left,mid,right = [],[],[]
        for i in nums:
            if i < pivot: left.append(i)
            elif i > pivot: right.append(i)
            elif i == pivot: mid.append(i)

        if len(right) >= k: pivot = self.findKthLargest(right, k)
        elif len(right) + len(mid) < k: pivot = self.findKthLargest(left, k - len(right) - len(mid))

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

3. 剑指 Offer 40. 最小的k个数

3.1 题目大意

描述：给定整数数组 $arr$，再给定一个整数 $k$。

要求：返回数组 $arr$ 中最小的 $k$ 个数。

说明：

• $0\le k\le arr.length\le 10000$。
• $0\le arr[i]\le 10000$。

示例：

• 示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
1
2

• 示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]
1
2

解题思路

同样只是简单的排序即可，这里使用堆排序简单演示一下

我的题解

class Solution(object):
    def inventoryManagement(self, stock, cnt):
        """
        :type stock: List[int]
        :type cnt: int
        :rtype: List[int]
        """
        if cnt == 0:
            return list()

        hp = [-x for x in stock[:cnt]]
        heapq.heapify(hp)
        for i in range(cnt, len(stock)):
            if -hp[0] > stock[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -stock[i])
        ans = [-x for x in hp]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18