首页 > 试题广场 >

数组Mex

[编程题]数组Mex

热度指数：10726 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请设计一个高效算法，查找数组中未出现的最小正整数。

给定一个整数数组A和数组的大小n，请返回数组中未出现的最小正整数。保证数组大小小于等于500。

测试样例：

[-1,2,3,4],4

返回：1

算法知识视频讲解

/*分析：

* 最小的没有出现的正整数

* 如果1没有出现那么最小结果为1

* 如果1到n都出现那么最下的结果为n+1

* 因此结果的范围1～n+1

* 数据范围最大500 数据不是很大可以考虑以空间换时间的做法

* 定义一个数组res[n] 遍历数组A 如果A[i]>n抛弃不会是结果如果A[i]<n res[A[i]]=1;

* 遍历res 为0的输出下标即为结果*/

public int findArrayMex(int[] A, int n) {

int[] res = new int[n];

for (int i = 0; i < n; i++) {

if (A[i]>0&&A[i]<=n){

res[A[i]-1]=1;

}

for (int i = 0; i < n; i++) {

if (res[i]==0){

return i+1;

}

return n+1;

}

发表于 2016-03-29 10:23:52 回复(10)

0pandas0

搬运一个代码过来：https://leetcode.com/discuss/24013/my-short-c-solution-o-1-space-and-o-n-time

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        // write code here
       for(int i = 0; i < n; ++ i)
            while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
                swap(A[i], A[A[i] - 1]);

        for(int i = 0; i < n; ++ i)
            if(A[i] != i + 1)
                return i + 1;

        return n + 1; 
    }
};

发表于 2016-05-02 14:28:46 回复(0)

C/C++

kakaan

使用了简单的排序，遍历，

    int findArrayMex(vector<int> A, int n) {
        sort(A.begin(),A.end());
        if(A[0]>1)return 1;
        for(int i=1;i<n;i++)
            if(A[i]-A[i-1] > 1)
                return A[i-1]+1;
        return A[n-1]+1;
    }

发表于 2016-09-05 11:43:38 回复(6)

Java

搬砖炫富

/*竟然和高票方法差不多，很简单，时间和空间复杂度都是O(n)，
看到的人麻烦点赞一下，让更多的人看到。不用排序，最多500个数据，最差的情况是
1-500都有，那么就返回501，否则返回第一个值为0的数组坐标就好。*/ 
import java.util.*;
public class ArrayMex {
    public int findArrayMex(int[] A, int n) {
        int j=1;
        int[] arr =new int[n+1];
        for(int i=0;i<n;i++){
            if(A[i]>0&&A[i]<=n){
                arr[A[i]]++;
            }
        }
        for( j=1;j<arr.length;j++){
            if(arr[j]==0)
                return j;
        }
        return j+1;
    }
}

编辑于 2018-07-25 16:26:34 回复(1)

Python

华科平凡

python solution easy to understand：

class ArrayMex:
    def findArrayMex(self, A, n):
        test = [False] * (n + 1)
        for i in A:
            if i > 0: test[i] = True
        for i, v in enumerate(test):
            if i > 0 and v == False:
                return i

发表于 2017-09-12 12:08:55 回复(2)

kestars

import java.util.*;

public class ArrayMex {
    public int findArrayMex(int[] A, int n) {
        // write code here
        HashMap<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            hashMap.put(A[i],1);
        }
        for(int i=1;i>0;i++){
            if(hashMap.get(i)==null){
                return i;
            }
        }
        return 1;
    }
}

发表于 2018-10-12 19:33:56 回复(0)

盐加三勺

//一次遍历解决问题,复杂度为O(n)
import java.util.*;

public class ArrayMex {
    public int findArrayMex(int[] A, int n) {
        // write code here
        Arrays.sort(A);
        int i = 0,j = 0;
        while(i < n){
            //除去非正数
            if(A[i] <= 0){
                i++;
                j++;
                continue;
            }
           //第一个整数如果大于1，就返回1；
            if(A[j] > 1){
                return 1;
            }
            //到达边界
            if(i + 1 == n){
                return A[n -1] + 1;
            }
            //中间部分
            if(A[i+1] - A[i] > 1){
                return A[i] + 1;
            }
            i++;
        }
        return 1;
    }
}

发表于 2017-08-04 20:47:26 回复(3)

尼见

时间复杂度为o(n^2)，还可以接受，方法比较简单。

public class ArrayMex {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] = { 1, 5, 3, 0, 6, 6, 6 };
		new ArrayMex().findArrayMex(a, 7);
	}

	public int findArrayMex(int[] A, int n) {
		// write code here

		int min = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - i - 1; j++) {
				if (A[j] > A[j + 1]) {
					int temp = A[j];
					A[j] = A[j + 1];
					A[j + 1] = temp;
				}
			}
		}

		int result = 1;
		for (int i = 0; i < n; i++) {
			if (A[i] == result) {
				i = 0;
				result++;
			}
		}

		return result;
	}
}

编辑于 2016-04-27 15:14:08 回复(2)

吾生有你

import java.util.*;

public class ArrayMex {
    public int findArrayMex(int[] A, int n) {
        // write code here
        TreeSet<Integer> tr=new TreeSet<>();   //去重
        for(int elem: A)
            tr.add(elem);
        int[] B=new int[tr.size()];  //将去重后的数据重新赋值一个数组中
        int k=0;
        for(int elem: tr)
            B[k++]=elem;
        
        int index=0;
        while(index<B.length && B[index]<=0)   //找到数组B中，第一个为整数的下标
            index++;
        int i=1;
        while(index<B.length && B[index]==i){  //返回数组中未出现的最小正整数i
            index++;
            i++;
        }
        return i;
    }
}

发表于 2018-06-28 20:26:32 回复(0)

XiaoyueDuan

解题思路：

因为输入不会超过500个数据，那么使用哈希表的想法，以空间换时间。

生成一个hash[500]的数组，初始化为0。从头遍历A，如果A[i]的值大于0，则相应hash[i-1]++。当遍历完整个数组后，hash[i]的值代表i+1这个数字在A中出现过的次数。

举例：

A={4,1,5,2,-1,4}

num 1 2 3 4 5

index 0 1 2 3 4

hash(前五个) 1 1 0 2 1

发现hash中index=2，num=3时为0，意味着最小的正整数没出现过。

时间和空间复杂度为O(n)。

#include <vector>

using namespace std;

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        // write code here
        vector<int> hash(500,0);
        for(int i=0;i<n;++i)
        {
            if(A[i]<=0)
                continue;

            ++hash[A[i]-1];
        }

        for(int i=0;i<500;++i)
        {
            if(hash[i]==0)
                return i+1;            
        }
        return -1;
    }
};

编辑于 2018-03-04 20:55:07 回复(0)

讲道理的牛肉丸顶呱呱

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        // write code here
        sort(A.begin(),A.end());
        A.erase(unique(A.begin(),A.end()),A.end());
        if(A.empty()||n<=0)return 1;
        if(A[0]>1) return A[0]-1;
        if(A[n-1]<1) return 1;
        for(int i=0;i<n-1;i++)
        {
            if(A[i+1]!=A[i]+1)
                return A[i]+1;
        }
        return A[n-1]+1;
    }
};

发表于 2018-02-07 11:18:12 回复(0)

C/C++

nbgao

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        int r[n];
        memset(r,0,sizeof(r));
        for(int i=0;i<n;i++)
            if(A[i]>0 && A[i]<=n)
                r[A[i]-1] = 1;
        
        for(int i=0;i<n;i++)
            if(r[i]==0)
                return i+1;
        
        return n+1;
    }
};

发表于 2017-11-10 01:47:33 回复(0)

acceptedYes

代码写的不够简洁！
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
//首先去掉重复的， 然后考虑各个情况！可以参考测试数据
int findArrayMex(vector<int> A, int n) {
    vector<int> B;
    for(int i = 0; i < n; i++) {
        if(A[i] > 0) {
            B.push_back(A[i]);
        }
    }
    sort(B.begin(), B.end());
    if(B.empty()) return 1;
    else if(B[0] > 1) return 1;
    else if(B.size()== 1) return 2;
    for(int i = 1; i < (int)B.size(); i++) {
        if(B[i-1]+1 < B[i]) {
            return B[i-1]+1;
        }
    }
    return B[B.size()-1]+1;
}


int main()
{
    //int arr[] = {-1,2,3,4};
    //int arr[] = {-2,-1,0,1};
    //int arr[] = {-2,-1,0,1, 3};
    // int arr[] = {-2,-1,0,1, 2};
    //int arr[] = {-1,2,3,4};
    //int arr[] = {2, 3, 4, 5};
    // int arr[] = {1, 2, 3, 4, 5};
    int arr[] = {-1, 0, 1, 1, 2, 2, 2, 4, 4, 5};
    int len = sizeof(arr)/sizeof(int);
    vector<int> A(arr, arr+len);
    int res = findArrayMex(A, A.size());
    cout << res << endl;
    return 0;
}

编辑于 2017-08-04 14:53:52 回复(0)

哇咔哇咔

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        // write code here
        vector<int> tmp(n,0);
        for(auto val:A)
        {
            if(val>=0 && val<=n)//记录0到n范围内的数
                tmp[val]=1;
        }
        for(int i=1;i<n;++i)//从1开始处理（剩个0，后续处理）
        {
            if(tmp[i]==0)
                return i;
        }
        return tmp[0]==1?n:n+1;//判断数组是否从0开始
    }
};

编辑于 2017-07-29 15:51:33 回复(0)

...王嘉廉睿

import java.util.*;

public class ArrayMex {
    public int findArrayMex(int[] A, int n) {
        int max = A[0];
        for(int i=0;i<n;i++)
            if(max<A[i])
            	max=A[i];
        int[] a = new int[max+1];
        for(int i=0;i<n;i++){
            if(A[i]<=0)
                continue;
            else
                a[A[i]]++;
        }
        for(int i=1;i<=max;i++)
            if(a[i]==0)
                return i;
        return  max+1;
        
    }
}

发表于 2016-12-29 16:14:09 回复(0)

Python

questRush

class ArrayMex:
    def findArrayMex(self, A, n):
        i = 0
        items = A 
        for j in xrange(n):
            if n >= items[j] > 0:
                items[i] = items[j]
                i += 1
        for k in xrange(i):
            v = abs(items[k])
            items[v - 1] = - abs(items[v - 1])
        for w in xrange(i):
            if items[w] > 0:
                return w + 1
        return i + 1

编辑于 2017-04-02 18:47:10 回复(0)

会呼吸旳痛

//先排序N*log(N),然后找到第一个整数的位置，后面依次寻找
//总的复杂度是 N*log(N)
class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        // write code here
        sort(A.begin(),A.end());
        int j;
        for(j=0;j<A.size();j++)
            {
            if(A[j]>0)break;
        }
            
        int i=1;
        int c=j;
        while(c<n)
            {
            if(c==j && A[c]!=i)break;
            else if(c>j && A[c] != A[c-1] && A[c]!=i)break;
            else if(c>j && A[c] == A[c-1] && A[c]!=i){c++;}
            else {c++;i++;}
        }
        return i;
    }
};

发表于 2016-09-06 11:44:43 回复(0)

★☆


	



	



	classArrayMex {



	public:



	    intfindArrayMex(vector<int> A, intn) {



	        // write code here



	        //排序并拷贝到set中去除重复的元素：



	        std::sort(A.begin(),A.end());



	        std::set<int> iset(A.begin(),A.end());



	        //从大于0的数字开始，逐个和1、2、3、4。。。比较，有未出现的即输出；



	        int j = 1;



	        for(auto it = iset.begin(); it != iset.end(); ++it){



	            if(*it > 0)



	                if(*it == j)



	                    j++;



	                else



	                    break;



	            elsecontinue;



	        }



	        returnj;



	    }



	};

提交了才发现原来数字还有重复的，果断用了set。本人愚笨，只会用库，轻喷。

发表于 2016-09-06 01:21:45 回复(0)

C/C++

想回老家的潜伏者躺平又起来了

利用哈希查找，时间复杂度为O(n)。

class ArrayMex {
public:
    int findArrayMex(vector<int> A, int n) {
        int hash[10000]={0};
        for(int i=0;i<n;i++){
            if(A[i]>0){
                hash[A[i]]=1;}
        }
        int number = 1;
        while(hash[number++]);//找到第一个没有出现的number,即hash[number]=0,跳出循环。
         return number-1;//因为最后找到时number+1了，所以返回number-1。
    }     
};

发表于 2016-08-10 11:49:16 回复(4)

已注销

//大家好，这个题目和今年网易内推的一个题目（重考的题目）解法一样；
class ArrayMex {
public:
    int findArrayMex(vector<int> vec, int n) 
    {
        // write code here
   sort(vec.begin(),vec.end());
   int i;
   int res=1;//最小正整数为1
   if(vec[0]>=2) return res;
   for(i=0;i<n-1;i++)
   {
   	  if(vec[i+1]-vec[i]>1)
      {
      	  if(vec[i]<=0 && vec[i+1]>1)
      	  {
      	  	  res=1;
      	  	  break;
		  }
		  else if(vec[i]>=0)
		  {
                     res=vec[i]+1;
		     break;
		  }
		  else
		  {
		  	 continue;
		  }
	  }
   }
   if(i>=n-2)
        res=vec[n-1]+1;
    return res;

    }
};

发表于 2016-08-08 21:17:08 回复(0)