Find first unique integer in a stream.


  • 0
    M

    Design a data structure that support the following methods:
    insert(int n); add integer n to a stream of integers.
    getFirstUniqueInteger(); return the first unique integer in the stream if found else return -1.

    Example:
    for input sequence:

    insert(2) // 2
    insert(2) // -1
    insert(3) // 3
    insert(4) // 3
    insert(3) //4


  • 1

    My idea is to use a list to store all unique values and use a hash map to record their positions in list (Note: use end() position for duplicated values)

    class MyContainer {
      private: list<int> unique; // all unique values by insertion order
               unordered_map<int, list<int>::iterator> pos; // map value to position in list "unique" 
      public: // using default constructor  
      int getFirstUniqueInteger() { return unique.empty()? -1 : unique.front(); }
      
      void insert(int x) {
          // insert new unique value to the tail of list and point to tail position
          if (!pos.count(x)) { unique.push_back(x); pos[x] = --unique.end(); } 
          // ignore already duplicated value
          else if (pos[x] == unique.end()) return;
          else { unique.erase(pos[x]); pos[x] = unique.end(); }
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.