8 ms·
Does it? Set insertion is O(log n) and you need to insert n items.
by trinovantes 4y ago
Does it? Set insertion is O(log n) and you need to insert n items.
- orlp 4y agoNot if you use a hash set. This is expected O(n) time to de-duplicate an array of integers while maintaining the original order (more explicitly written than I normally would in Rust for didactical purposes): let mut hash_set = HashSet::new(); let mut len = 0; for i in 0..arr.len() { if !hash_set.contains(&arr[i]) { hash_set.insert(arr[i]); arr[len] = arr[i]; len += 1; } } arr.truncate(len);
- trinovantes 4y agoGood point but it's not exactly a free lunch. You're trading memory for the speedup. You can also use radix sort for what I'd like to call "fake" O(n) sort since physical hardware puts an upper limit on the hidden constant.
- saagarjha 4y agoRadix sort generally places far more restrictions on the keys than a set would.
- Cyphonetic 4y agoBut to order a list is O(n log n)
- trinovantes 4y agoIn the worst case, you need to insert every element into your set to find out if there's no duplicate hence it'll take O(n log n) too
- pclmulqdq 4y agoNot with a hash set - that gives you expected amortized O(1) insertion (yes, both expected and amortized). In contrast, a generalized sort is O(n log n), but you can sort numeric types in O(n).