跳转至

2349. 设计数字容器系统

题目描述

设计一个数字容器系统，可以实现以下功能：

  • 在系统中给定下标处 插入 或者 替换 一个数字。
  • 返回 系统中给定数字的最小下标。

请你实现一个 NumberContainers 类：

  • NumberContainers() 初始化数字容器系统。
  • void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字。
  • int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。

 

示例：

输入：
["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]

解释：
NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ，所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。

 

提示：

  • 1 <= index, number <= 109
  • 调用 change 和 find 的 总次数 不超过 105 次。

解法

方法一：哈希表

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


class NumberContainers:
    def __init__(self):
        self.mp = {}
        self.t = defaultdict(SortedSet)

    def change(self, index: int, number: int) -> None:
        if index in self.mp:
            v = self.mp[index]
            self.t[v].remove(index)
        self.mp[index] = number
        self.t[number].add(index)

    def find(self, number: int) -> int:
        s = self.t[number]
        return s[0] if s else -1


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

 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
class NumberContainers {
    private Map<Integer, Integer> mp = new HashMap<>();
    private Map<Integer, TreeSet<Integer>> t = new HashMap<>();

    public NumberContainers() {
    }

    public void change(int index, int number) {
        if (mp.containsKey(index)) {
            int v = mp.get(index);
            t.get(v).remove(index);
            if (t.get(v).isEmpty()) {
                t.remove(v);
            }
        }
        mp.put(index, number);
        t.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        return t.containsKey(number) ? t.get(number).first() : -1;
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index,number);
 * int param_2 = obj.find(number);
 */

 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
class NumberContainers {
public:
    map<int, int> mp;
    map<int, set<int>> t;

    NumberContainers() {
    }

    void change(int index, int number) {
        auto it = mp.find(index);
        if (it != mp.end()) {
            t[it->second].erase(index);
            it->second = number;
        } else
            mp[index] = number;
        t[number].insert(index);
    }

    int find(int number) {
        auto it = t.find(number);
        return it == t.end() || it->second.empty() ? -1 : *it->second.begin();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

 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
type NumberContainers struct {
    mp map[int]int
    t  map[int]*redblacktree.Tree
}

func Constructor() NumberContainers {
    return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree{}}
}

func (this *NumberContainers) Change(index int, number int) {
    if num, ok := this.mp[index]; ok {
        this.t[num].Remove(index)
    }
    this.mp[index] = number
    if this.t[number] == nil {
        this.t[number] = redblacktree.NewWithIntComparator()
    }
    this.t[number].Put(index, nil)
}

func (this *NumberContainers) Find(number int) int {
    s, ok := this.t[number]
    if !ok || s.Size() == 0 {
        return -1
    }
    return s.Left().Key.(int)
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Change(index,number);
 * param_2 := obj.Find(number);
 */

评论