Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

Problem:

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. 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.

Idea:

Hashtable + array

Solution:

 

Java

 

Related Problems:

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) – Add a integer number from the data stream to the data structure.
  • double findMedian() – Return the median of all elements so far.

For example:

 

Idea:

  1. Min/Max heap
  2. Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)

Solution1:

 

Solution 2:

 

Related Problems

花花酱 Leetcode 140. Word Break II

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

Python3

 

Related Problems