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 次。

解题思路与题解

方法一

暴力法（超时）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode2042 {

    public static void main(String[] args) {
        NumberContainers nc = new NumberContainers();
        System.out.println(nc.find(10));
        nc.change(2, 10);
        nc.change(1, 10);
        nc.change(3, 10);
        nc.change(5, 10);
        System.out.println(nc.find(10));
        nc.change(1, 20);
        System.out.println(nc.find(10));
    }

}


class NumberContainers {

    private final Map<Integer, List<Integer>> value_index_map;
    private final Map<Integer, Integer> index_value_map;


    public NumberContainers() {
        value_index_map = new HashMap<>();
        index_value_map = new HashMap<>();
    }

    public void change(int index, int number) {
        if (index_value_map.containsKey(index)) {
            int old_number = index_value_map.get(index);
            value_index_map.get(old_number).remove(Integer.valueOf(index));
            if (value_index_map.get(old_number).isEmpty()) {
                value_index_map.remove(old_number);
            }
        }
        index_value_map.put(index, number);
        value_index_map.computeIfAbsent(number, k -> new ArrayList<>()).add(index);
        value_index_map.get(number).sort(Integer::compareTo);
    }

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

}

方法二

优先队列 + 惰性删除

使用哈希表 nums 记录每个下标对应的数字，同时使用哈希表 + 优先队列（最小值）记录每个数字对应的下标集合。

change 函数：

记录 nums[index]=number，同时将 index 压入 number 对应的优先队列中。

find 函数：

change 函数在替换给定下标处的数字时，没有先删除对应优先队列中的下标。因此我们在获取 number 的下标最小值时，需要先校验优先队列堆顶下标对应的数字是否等于 number，不等于时直接丢弃，等于则返回该下标。如果优先队列为空，则返回 −1。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode2042 {

    public static void main(String[] args) {
        NumberContainers nc = new NumberContainers();
        System.out.println(nc.find(10));
        nc.change(2, 10);
        nc.change(1, 10);
        nc.change(3, 10);
        nc.change(5, 10);
        System.out.println(nc.find(10));
        nc.change(1, 20);
        System.out.println(nc.find(10));
    }

}

class NumberContainers {
    private final Map<Integer, Integer> nums = new HashMap<>();
    private final Map<Integer, PriorityQueue<Integer>> heaps = new HashMap<>();

    public void change(int index, int number) {
        nums.put(index, number);
        heaps.computeIfAbsent(number, k -> new PriorityQueue<>()).add(index);
    }

    public int find(int number) {
        PriorityQueue<Integer> heap = heaps.get(number);
        if (heap == null) {
            return -1;
        }
        while (!heap.isEmpty() && !nums.get(heap.peek()).equals(number)) {
            heap.poll();
        }
        return heap.isEmpty() ? -1 : heap.peek();
    }
}