Problem

Design a number container system that can do the following:

  • Insert or Replace a number at the given index in the system.
  • Return the smallest index for the given number in the system.

Implement the NumberContainers class:

  • NumberContainers() Initializes the number container system.
  • void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
  • int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

https://leetcode.com/problems/design-a-number-container-system/

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]
Explanation

1
2
3
4
5
6
7
8
9
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20.
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

Constraints:

  • 1 <= index, number <= 10⁹
  • At most 10⁵ calls will be made in total to change and find.

Test Cases

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

def __init__(self):


def change(self, index: int, number: int) -> None:


def find(self, number: int) -> int:



# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import pytest

from solution import NumberContainers

null = None


@pytest.mark.parametrize('actions, params, expects', [
(
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"],
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]],
[null, -1, null, null, null, null, 1, null, 2],
),
])
@pytest.mark.parametrize('clazz', [NumberContainers])
def test_solution(clazz, actions, params, expects):
sol = None
for action, args, expected in zip(actions, params, expects):
if action == 'NumberContainers':
sol = clazz(*args)
else:
assert getattr(sol, action)(*args) == expected

Thoughts

3160. Find the Number of Distinct Colors Among the Balls 差不多。index 相当于球的编号,number 相当于颜色。主要的区别是本题需要记录每个 number 对应的 index 数组,以便随时可以查询此 number 所在的所有 index 的最小值。

同样用字典记录每个 index 最新的 number。再用字典记录每个 number 的所有 index,用有序数组记录,这里直接用 Python 的 list。需要增加或删除的时候,先用二分法查找再执行插入或删除操作。

构造函数的时间复杂度 O(1)change 方法的时间复杂度 O(n)find 方法的时间复杂度 O(n)。空间复杂度 O(n)。其中 n 是 change 的调用次数。

Code

solution.py
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
from bisect import bisect_left
from collections import defaultdict


class NumberContainers:

def __init__(self):
self._numbers: dict[int, int] = {} # index -> number
self._indices: dict[int, list[int]] = defaultdict(list) # number -> sorted list of indices

def change(self, index: int, number: int) -> None:
if index in self._numbers and self._numbers[index] == number:
return

if index in self._numbers:
old_number = self._numbers[index]
indices = self._indices[old_number]
del indices[bisect_left(indices, index)]

self._numbers[index] = number
indices = self._indices[number]
indices.insert(bisect_left(indices, index), index)

def find(self, number: int) -> int:
if number not in self._indices:
return -1

indices = self._indices[number]
if not indices:
return -1

return indices[0]


# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)