摘要:題目要求設(shè)計一個數(shù)據(jù)結(jié)構(gòu),支持能夠在的時間內(nèi)完成對數(shù)字的插入,刪除和獲取隨機數(shù)的操作,允許插入重復(fù)的數(shù)字,同時要求每個數(shù)字被隨機獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個數(shù)成正比。網(wǎng)上有一些實現(xiàn)采用來解決,這是不合理的。此時的代碼如下
題目要求
Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed. insert(val): Inserts an item val to the collection. remove(val): Removes an item val from the collection if present. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains. Example: // Init an empty collection. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1); // getRandom should return 1 and 2 both equally likely. collection.getRandom();
設(shè)計一個數(shù)據(jù)結(jié)構(gòu),支持能夠在O(1)的時間內(nèi)完成對數(shù)字的插入,刪除和獲取隨機數(shù)的操作,允許插入重復(fù)的數(shù)字,同時要求每個數(shù)字被隨機獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個數(shù)成正比。
強烈建議先看一下這個問題的基礎(chǔ)版本,傳送門在這里。
思路和代碼遵循之前基礎(chǔ)版本的思路,當(dāng)解決這種問題的時候我們會用數(shù)組和hashmap來做位置的存儲,從而更新的時候無需檢索。但是在這題的情境下,存在一個問題,舉個例子:
假如現(xiàn)在插入1,2,3,3,4,3,3
此時的map中應(yīng)當(dāng)是如下:1:[0] 2:[1] 3:[2,3,5,6] 4:[4]
我們先執(zhí)行刪除1,按照之前的規(guī)則,我們會刪除數(shù)組中最后一個元素,并將其值移動到這個位置上map應(yīng)當(dāng)被更新為2:[1] 3:[2,3,5,0] 4:[4]
接著我們再刪除2,此時雖然最后一個元素還是3,但是這個3在位置數(shù)組中的位置卻是需要O(n)的時間來查詢的,這就違反了O(1)的刪除時間復(fù)雜度。
網(wǎng)上有一些java實現(xiàn)采用OrderSet來解決,這是不合理的。因為有序堆本質(zhì)上底層是一個最大堆或最小堆,它的插入和刪除操作都需要O(lgn)的時間復(fù)雜度來完成
這里我們采用的方式是繼續(xù)冗余,即我們在插入每一個元素的時候,同時記錄該元素在下標數(shù)組中的位置,舉個例子:
先插入1,則map的值為[1:[0]],list的值為[[1,0]] 此處的0代表1這個值在下標數(shù)組[0]中位于第0個位置上。
在插入2,則map的值為[1:[0], 2:[1]], list的值為[[1,0],[2,0]]
再插入1,此時map=[1:[0, 2], 2:[1], list的值為[[1,0],[2,0],[1,1]]
此時刪除2,同理,我們還是會將數(shù)組中最后一個元素的值替換在刪除掉元素的位置,此處我們從map中得出2最后一次在數(shù)組中出現(xiàn)的下標為1,我們需要將最后位置上的1替換掉當(dāng)前2的值,之后我們還能從數(shù)組中得知,1這個數(shù)字它對應(yīng)的位置下標的索引為2,因此我們再將map[1]中map[1][2]的值替換為2所在的新的位置,即1。此時的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]
代碼如下:
public class InsertDeleteGetRandomDuplicatesallowed_381 { private Listlist; private Map > index; /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ public InsertDeleteGetRandomDuplicatesallowed_381() { list = new ArrayList<>(); index = new HashMap<>(); } public boolean insert(int val) { boolean contains = true; if(!index.containsKey(val) || index.get(val).isEmpty()) { contains = false; } List tmp = index.getOrDefault(val, new ArrayList<>()); tmp.add(list.size()); index.put(val, tmp); list.add(new Pair(val, tmp.size()-1)); return !contains; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ public boolean remove(int val) { if(!index.containsKey(val) || index.get(val).isEmpty()) { return false; } List tmp = index.get(val); int position = tmp.remove(tmp.size()-1); if(position != list.size()-1) { Pair lastPair = list.get(list.size()-1); int lastValue = lastPair.value; List lastValuePositions = index.get(lastValue); lastValuePositions.set(lastPair.position, position); list.set(position, lastPair); } list.remove(list.size()-1); return true; } /** Get a random element from the collection. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position).value; } public static class Pair{ int value; int position; public Pair(int value, int position) { this.value = value; this.position = position; } } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/73269.html
摘要:思路可以實現(xiàn)時間復(fù)雜度的和,但是要求也是,只用是不可以的。但是在里面查找的時間復(fù)雜度依然是,可以想到用來記錄對應(yīng)的,這樣查找的時間也是常數(shù)。用可以保持順序,但是的時間復(fù)雜度是。 380. Insert Delete GetRandom O(1) Design a data structure that supports all following operations in aver...
摘要:題目要求設(shè)計一個數(shù)據(jù)結(jié)構(gòu),使得能夠在的時間復(fù)雜度中插入數(shù)字,刪除數(shù)字,以及隨機獲取一個數(shù)字。因此,使用來查詢時不可避免的。如何實現(xiàn)的隨機查詢這個其實就是強調(diào)一點,我們需要維持原有的插入順序,從而保證各個元素等概率被隨機。 題目要求 Design a data structure that supports all following operations in average O(1)...
摘要:題目鏈接直接用一個,結(jié)果了看了加了個,不過感覺沒什么必要加,反正保存的都一樣,只是的時間大于,用可以保證。看了題目條件是可以隨便返回一個值,但是不讓這么做。很無語啊如果這道題要求要求的是的,那就和一樣了。 Design Phone Directory 題目鏈接:https://leetcode.com/problems... 直接用一個set,結(jié)果tle了= = public clas...
摘要:哈希函數(shù)與哈希表一哈希函數(shù)哈希函數(shù)性質(zhì)輸入域是無窮的輸出域有窮的當(dāng)輸入?yún)?shù)固定的情況下,返回值一定一樣當(dāng)輸入不一樣,可能得到一樣的值。 哈希函數(shù)與哈希表 一、哈希函數(shù) 1.1 哈希函數(shù)性質(zhì): input輸入域是無窮的 output輸出域有窮的 當(dāng)輸入?yún)?shù)固定的情況下,返回值一定一樣 當(dāng)輸入不一樣,可能得到一樣的值。(必然會出現(xiàn),因為輸入域很大,輸出域很小),產(chǎn)生哈希碰撞 均勻分布的特...
摘要:復(fù)雜度思路考慮用二維來表示變換的情況。如果兩個字符串中的字符相等,那么如果兩個字符串中的字符不相等,那么考慮不同的情況表示的是,從字符串到的位置轉(zhuǎn)換到字符串到的位置,所需要的最少步數(shù)。 LeetCode[72] Edit Distance Given two words word1 and word2, find the minimum number of steps require...
閱讀 2508·2023-04-26 02:47
閱讀 2999·2023-04-26 00:42
閱讀 865·2021-10-12 10:12
閱讀 1372·2021-09-29 09:35
閱讀 1689·2021-09-26 09:55
閱讀 478·2019-08-30 14:00
閱讀 1532·2019-08-29 12:57
閱讀 2350·2019-08-28 18:00