目录

  • 打乱数组
  • 最小栈

打乱数组

题目描述

给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

  • Solution(int[] nums) 使用整数数组 nums 初始化对象
  • int[] reset() 重设数组到它的初始状态并返回
  • int[] shuffle() 返回数组随机打乱后的结果

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]

输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如,返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如,返回 [1, 3, 2]

提示

  • 1 <= nums.length <= 200
  • -106 <= nums[i] <= 106
  • nums 中的所有元素都是 唯一的
  • 最多可以调用 5 * 104 次 reset 和 shuffle

题解

一开始没太理解这道题的意图,直接调用random.shuffle()就结束了。
原来目的在于自己实现打乱数组的方法。

暴力抽奖法

第一种暴力方法就是,将原数组看做一个“箱子”,然后对箱子中的所有元素进行不放回抽奖。全部抽完了就得到了一个打乱的数组。
类中保留一个原始数组,reset()的时候直接返回原始数组即可。
另外拷贝一个数据,用于打乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
self.shuffled_nums = list(nums)

def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums

def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
buff = list(self.nums) # 假设为抽奖“盒子”
for i in range(len(self.nums)):
popid = random.randrange(len(buff)) # 在元素范围内选取一个随机数
self.shuffled_nums[i] = buff.pop(popid) # 不放回抽样
return self.shuffled_nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

Fisher-Yates 洗牌算法

从题解中学到了该算法。
前面暴力的方法因为每次都需要修改buff列表,总共要修改n次,因此时间复杂度为$O(n^2)$。
该方法不需要对原始列表进行修改,因此将时间复杂度优化到$O(n)$。
总体思想就是,对每个元素,与后面的随机元素进行交换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
self.shuffled_nums = list(nums)


def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums


def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
buff = list(self.nums)
for i in range(len(self.nums)):
popid = random.randrange(i, len(buff)) # randrange的范围为左闭右开
self.shuffled_nums[i], self.shuffled_nums[popid] = self.shuffled_nums[popid], self.shuffled_nums[i] # 交换两元素的位置
return self.shuffled_nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

最小栈

题目描述

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

题目中保证pop、top 和 getMin 操作总是在 非空栈 上调用。

题解

这个题的解法就非常多了。可以比较自由地进行设计。

栈 + 哈希表

这里提出一个比较基本的方法,使用普通的栈和哈希表实现该操作。
push, pop, top的操作就是普通栈的操作,因此一个主要问题就是实现对于栈中最小元素的访问问题。因此这里使用一个哈希表来保存栈中每个元素及其对应出现的次数。在访问最小元素的时候,对哈希表中所有元素进行排序,取最小的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class MinStack:

def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.dic = {}


def push(self, val: int) -> None:
self.stack.append(val)
self.dic[val] = self.dic.get(val, 0) + 1


def pop(self) -> None:
toPop = self.stack.pop(-1)
self.dic[toPop] = self.dic[toPop] - 1
if self.dic[toPop] == 0:
self.dic.pop(toPop)


def top(self) -> int:
return self.stack[-1]


def getMin(self) -> int:
# 可以自己实现取最小值,或者直接使用sorted进行排序,返回最小值
# 测试中直接使用sorted排序反而更快一点。

# m = list(self.dic.keys())[0]
# for i in self.dic.keys():
# m = min(m, i)
return sorted(self.dic.keys(), reverse=False)[0]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

但是这种方法实际上是无法满足getMin()的常数时间复杂度的。因为需要涉及到遍历或者排序的过程。

双栈法

对于原始栈(记为stack),额外使用一个栈(记为minStack),用来保存原始栈中对应位置元素对应的最小值。
入栈时:将目标数入栈,然后比较目标数与当前最小值(即minStack的栈顶元素)的大小,将较小的入栈minStack。
出栈时:同时出栈stack和minStack。
这样在访问最小值时,只需要访问minStack的栈顶元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minStack = []

def push(self, val: int) -> None:
if len(self.stack) == 0:
self.stack.append(val)
self.minStack.append(val)
else:
curmin = self.minStack[-1]
curmin = min(curmin, val)
self.stack.append(val)
self.minStack.append(curmin)

def pop(self) -> None:
self.stack.pop(-1)
self.minStack.pop(-1)

def top(self) -> int:
return self.stack[-1]

def getMin(self) -> int:
return self.minStack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()