CareerCup Find the biggest interval that has all its members in list in O(n)

Given a list of integers, find out the biggest interval that has all its members in the given list. e.g. given list 1, 7, 4, 6, 3, 10, 2 then answer would be [1, 4]. Develop algorithm and write code for this

-------------------------------------------------------------------------

What is biggest interval? It means the longest consecutive integers. Take the above example, 1, 2, 3, 4 are members of the list.

#include<iostream>
#include<stdio.h>
#include<stack>
#include<vector>
#include<string>
#include<unordered_set>
#include<unordered_map>


#include<set>


#include<queue>
#include<map>


using namespace std;
class Solution {
 public:
  void largestRange(vector<int>& lst, vector<int>& range) {
    unordered_set<int> table;
    range[0] = 0;
    range[1] = -1;
    int size = lst.size(), i, j, cur, a, b;
    for (i = 0; i < size; ++i) 
      table.insert(lst[i]);
   
    for (unordered_set<int>::iterator it = table.begin(); table.size() > 0; it = table.begin()) {
      cur = *it;
      table.erase(it);
      for (i = cur + 1; table.size() > 0; ++i) {
        if (table.find(i) == table.end())
          break;
        table.erase(i);
      }
      b = i - 1;
      for (j = cur - 1; table.size() > 0; --j) {
        if (table.find(j) == table.end())
          break;
        table.erase(j);
      }
      a = j + 1;
	  if (b - a > range[1] - range[0]) {
	    range[1] = b;
	    range[0] = a;
      }
    }
  }
};
int main() {
  Solution s;
  int a[] = {1, 7, 4, 6, 3, 10, 2};
  vector<int> v(a, a + 7);
  vector<int> range(2);
  s.largestRange(v, range);
  cout<<range[0]<<" "<<range[1]<<endl;
  
  return 0;
}


CareerCup Find the biggest interval that has all its members in list in O(n)

上一篇:小谈Java的初始化问题


下一篇:免费馅饼