NickFuryy's blog

How to find a mex of an array in short time?
By NickFuryy, history, 3 years ago, In English

Help pls!

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +32 Vote: I do not like it

You can keep an array of Boolean values, with each index representing whether or not you have seen this number in the array. It will be of size n+1, since mex of n elements is at most n+1. Fill this array in with a O(n) loop over the array, and then go over the Boolean array and find the first false value, that index will be your mex.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

If there are $$$Q$$$ mex queries of ranges in an array lengthened $$$N$$$, then it can be solved in $$$O(Q\sqrt N+N)$$$ with Mo's algorithm.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

in case of the given array is sorted, you can binary search on the first index that is not equal to it's value in the array, the answer will be that index. timeO(logN).

code
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    Besides being sorted, the array should only have unique values.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      this can be easily handled while taking the initial array.

      code
      → Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If you want to just find out the mex of the whole array, write a simple loop.

int mex(vector<int> vc) {
	vector<int> cnt;
	int n=vc.size(); cnt.resize(n+2);
	for(auto id:vc) if(vc<=n) cnt[id]=1;
	for(int i=0;i<=n;i++) if(cnt[i]==0) return i;
}

If you want to query the mex of an interval for many times, this problem may help. https://www.luogu.com.cn/problem/P4137

Sorry I don't know "可持久化线段树"'s English translation.

→ Reply