leetcode题解-380. Insert Delete GetRandom O(1)

2019-11-06 08:46:24

字体：大中小

来源：转载

供稿：网友

题目：Design a data structure that supports all following Operations in average O(1) time.

1，insert(val): Inserts an item val to the set if not already PResent. 2，remove(val): Removes an item val from the set if present. 3，getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

其实本题中所说的时间复杂度为o(1)，并不是真的意味着时间复杂度为o(1).因为不可能有某种数据结构可以实现插入删除查找等操作的时间复杂度均为o(1).这里的意思是说借助某种java内部的数据结构时，将其操作视为o(1)。考虑到题目中有查找的需求，所以我们使用HashMap可以简单的实现查找一个元素是否已经存在。此外，getRandom函数要返回一个随机元素，这里我们需要使用一个ArrayList数据结构存储每个元素，并使用Random函数产生随机数。代码入下：

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Random;public class RandomizedSet { ArrayList<Integer> nums = new ArrayList<>(); HashMap<Integer, Integer> map = new HashMap<>(); //stores indices /** Initialize your data structure here. */ public RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert(int val) { if(!map.containsKey(val)){ nums.add(val); map.put(val, nums.size()-1); return true; } return false; } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove(int val) { if(map.containsKey(val)){ int last = nums.get(nums.size()-1); int removePos = map.get(val); nums.set(removePos, last); //replace the removed number with the last number nums.remove(nums.size()-1); //always remove the last element, takes O(1) map.put(last, removePos); //upadate index map.remove(val); return true; } return false; } /** Get a random element from the set. */ public int getRandom() { int index = (int)(Math.random() * nums.size()); return nums.get(index); }}

这一次的程序运行更让我发现了运行时间的不稳定性，从35%到68%的波动实在是让人无法接受==

上一篇：N个点FFT变换中的频率分辨率以及与实际频率的关系

下一篇：软件开发基本认知观