遂宁商城网站建设方案,专业做域名的网站吗,伊春信息网,重庆小程序开发费用题目
设计一个数据结构#xff0c;使如下3个操作的时间复杂度都是O#xff08;1#xff09;。
insert#xff08;value#xff09;#xff1a;如果数据集中不包含一个数值#xff0c;则把它添加到数据集中。remove#xff08;value#xff09;#xff1a;如果数据集…题目
设计一个数据结构使如下3个操作的时间复杂度都是O1。
insertvalue如果数据集中不包含一个数值则把它添加到数据集中。removevalue如果数据集中包含一个数值则把它删除。getRandom()随机返回数据集中的一个数值要求数据集中每个数字被返回的概率都相同。
分析
由于题目要求插入和删除包括判断数据集中是否包含一个数值的时间复杂度都是O1能够同时满足这些时间效率要求的只有哈希表因此这个数据结构要用到哈希表。但是如果只用哈希表则不能等概率地返回其中的每个数值。
如果数值是保存在数组中的那么很容易实现等概率返回数组中的每个数值。假设数组的长度是n那么等概率随机生成从0到n-1的一个数字。如果生成的随机数是i则返回数组中下标为i的数值。由此可以发现需要结合哈希表和数组的特性来设计这个数据容器。
由于数值保存在数组中因此需要知道每个数值在数组中的位置否则在删除的时候就必须顺序扫描整个数组才能找到待删除的数值那就需要On的时间。通常把每个数值在数组中的位置信息保存到一个HashMap中HashMap的键是数值而对应的值为它在数组中的位置。
解
public class Test {public static void main(String[] args) {RandomizedSet randomizedSet new RandomizedSet();randomizedSet.insert(1);randomizedSet.insert(2);randomizedSet.insert(3);randomizedSet.insert(4);for (int i 0; i randomizedSet.nums.size(); i) {System.out.println(randomizedSet.nums.get(i));}System.out.println(-----------------------);randomizedSet.remove(2);for (int i 0; i randomizedSet.nums.size(); i) {System.out.println(randomizedSet.nums.get(i));}System.out.println(-----------------------);System.out.println(randomizedSet.getRandom());}static class RandomizedSet {HashMapInteger, Integer numToLocation;ArrayListInteger nums;public RandomizedSet() {numToLocation new HashMap();nums new ArrayList();}public boolean insert(int val) {if (numToLocation.containsKey(val)) {return false;}numToLocation.put(val, nums.size());nums.add(val);return true;}public boolean remove(int val) {if (!numToLocation.containsKey(val)) {return false;}int location numToLocation.get(val);numToLocation.put(nums.get(nums.size() - 1), location);numToLocation.remove(val);nums.set(location, nums.get(nums.size() - 1));nums.remove(nums.size() - 1);return true;}public int getRandom() {Random random new Random();int r random.nextInt(nums.size());return nums.get(r);}}
}
