Tìm số nguyên dương nhỏ nhất không chứa trong mảng đã cho

[vnkid (Trần Đức Vương)]

O(CONSTANT*n) về tổng thể sẽ thấp hơn O(n^2)

[rogp10]

max có phải là constant không? (mà mình cũng chê O(N^2)). Vì max này là phần tử lớn nhất đó.

Vậy thì sort O(N*logN) cho bền đẹp

[Chien_Bui (Chiến Bùi)]

#include<iostream>
#include<cstdlib> // thu vien nay la de su dung cu phap system("cls"); co tac dung xoa man hinh
using namespace std;
/*
Cach lam cua bai nay gom cac buoc:
 -sap xep cac phan tu trong mang theo thu tu tang dan
 -loai cac phan tu giong nhau ra khoi mang
 -neu hai phan tu lien tiep khong phai la hai so tu nhien lien tiep
  thi in ra so tu nhien tiep theo cua phan tu dau.
VD: arr[1]!=arr[2]//arr[1]==1,arr[2]==3
    thi in ra arr[1]+1//tuc la in ra so 2
*/
int main()
{
    int n,a,b,x,y;
	int arr[100];
	// nhap n khong am va cac phan tu cua mang
	do
	{
	system("cls");
	cout<<"Hay nhap so n khong am: ";
	cin>>n;
    }while(n<0);
	for(int i=0;i<n;i++)
	{
		cout<<"Nhap cac gia tri cua arr["<<i<<"] - cac gia tri nay se duoc chuyen thanh so duong:";
		cin>>b;
		arr[i]=abs(b);
	}
	// sap xep tang dan cac phan tu
	for(int i=0;i<n;i++)
	{
	   for(int j=0;j<n;j++)	
	   {
	   	if(arr[i]<arr[j])
	   	{
	   		a=arr[i];
	   		arr[i]=arr[j];
	   		arr[j]=a;
		}
	   }
	}
    //loai cac phan tu giong nhau
    for(int j=0;j<n;j++)
    {
	for(int i=0;i<n;i++)
	{
	    if(arr[i]==arr[i+1])
	    {
	    	x=i+1;
	    	for(x;x<n;x++)
	    	{
	    		arr[x]=arr[x+1];
			}
		 	n--;
		    
	    }
    }
    }
	// neu phan tu be nhat khong phai la 1 thi in 1 ra man hinh
	if(arr[0]!=1){cout<<1;}
	if(arr[0]==1)
	{
    // neu hai phan tu lien tiep khong phai la hai so tu nhien lien tiep thi in ra so tiep theo cua phan tu dau
    for(int i=0;i<n;i++)
    {
			if(arr[i]+1!=arr[i+1])
		{
			cout<<arr[i]+1;
			break;
	    }
    }
	}
	return 0;
}

[daothuan]

int SearchMinNonNeg (std::vector arr)
{
// Sort array
sort(arr.begin(), arr.end());
int size = arr.size();

int minNonNeg = 0;
for(int i=0; i < size; i++)
{
    if((arr[i] < 0) || ((arr[i] <= minNonNeg) && (arr[i] == arr[i+1])))
    {
        continue;
    }
    else if(arr[i] <= minNonNeg)
    {
        minNonNeg++;
    }
    else // minNonNeg is smaller than num
    {
        break;
    }
}

return minNonNeg;

}