Tìm số nguyên dương nhỏ nhất không có trong mảng

[giang3 (Giang11)]

Đề bài : Cho mảng a gồm n phần tử gồm cả số 0. Nhiệm vụ của bạn là tìm số nguyên dương nhỏ nhất không có mặt trong mảng
Ý tưởng: 1.Sắp xếp lại mảng
2. for từ 1 đến n+1
2.1 Nếu max của mảng nhỏ hơn 0 output 1
2.2 Nếu min của mảng lớn hơn 1 output 1
2.3 trường hợp còn lại thì nếu a[i] +1 !=a[i+1] thì output ra a[i]+1; break;
Ý tưởng trên chỉ đúng trong 1 số trường hợp ví dụ như ={ 1,2,3,4,5} output =6 nhưng trường hợp { -2 -1 -3 2 } thì output =3
Mọi người cho em xin ý kiến với ạ

[rogp10]

2.1 Nếu max của mảng nhỏ hơn 0 output 1
2.2 Nếu min của mảng lớn hơn 1 output 1

Hai bước này nên đưa lên đầu. Mảng chỉ là không giảm thôi nên bước 2.3 sẽ bị sót.

[giang3 (Giang11)]

vậy có thuật toán gì để hoàn thiện được các trường hợp còn lại không ạ

[DoTran1]

B1: sắp xếp tăng dần
B2. Bạn thử code này coi

code

if (a[0] > 1 || a[n-1] < 0){
  return result = 1;
}
for (i = 1; i < n - 1; i++){
   if (a[i] <= 0 && a[i+1] <= 0) {
       continue;
   }
   if (a[i] >= 0 && a[i] + 1 < a[i + 1]) {
     return result = a[i] + 1;
   }
}
return result = (a[i] + 1);

[8_Naf]

Bạn sort mảng rồi dùng hàm này, mình viết hàm này dựa trên ý tưởng của bạn ở trên và có cải tiến về hiệu suất một chút:

	if (0 == n) {
		return -1;
	}

	if (a[0] > 1 || a[n - 1] <= 0) {
		return 1;
	}
	
	//Giảm n đi 1, để điều kiện các vòng lặp bên dưới từ i < n - 1 trở thành i < n (tiết kiệm thời gian)
	--n;
	
	size_t i;
	
	//Hai dòng code sau là để làm cho mảng lúc nào cũng có số nguyên dương
	//Từ đó điều kiện của vòng for ở bên dưới từ a[i] < 0 && i < n - 1 trở thành a[i] < 0 (tiết kiệm thời gian)
	//Biến value_its để tránh mất giá trị của a[n - 1]
	int value_its = a[n]; //value_its = a[n - 1], do đã giảm n ở trên
	a[n] = 1; //Cho a[n - 1] = một số nguyên dương bất kì
	 
	//Chạy đến khi gặp số nguyên dương
	for (i = 0; a[i] <= 0; ++i);	
	
	//Sau khi duyệt xong thì trả lại giá trị cho a[n - 1]
	a[n] = value_its;
	
	//Nếu số nguyên dương đầu tiên của mảng > 1, thì số nguyên dương nhỏ nhất không xuất hiện trong mảng là 1
	if (a[i] > 1) {
		return 1;
	}
	
	for (; i < n; ++i) {
		//Nếu a[i + 1] - a[i] > 1, thì hai số này không phải là số liền kề, suy ra giữa chúng có một hoặc nhiều số nguyên khác
		//Vậy số cần tìm là a[i] + 1
		if (a[i + 1] - a[i] > 1) {
			return a[i] + 1;
		}
	}
	
	return a[i] + 1; //a[n - 1] + 1
}

[htwap (lu___va_sa__)]

sao hơi cực nhỉ, ý tưởng của mình là làm 1 mảng để đánh dấu các phần tử 0 đến n - 1 nằm trong mảng a, rồi tìm phần tử đầu tiên thuộc 0 … n - 1 mà không nằm trong a thôi.

mình viết tạm code kiểu như này nhé, chứ mấy năm rồi k code nó, chắc k chạy đc

int min_num(int a[], int n) {
  bool c[n] = {0};
  for (int i = 0; i < n; i++) {
    if (a[i] >= 0 && a[i] < n) {
      c[a[i]] = true;
    }
  }

  for (int i = 0; i < n; i++) {
    if (!c[i]) {
      return i;
    }
  }
  
  return 0;
}

[Tuyen_Hoang (Tuyền Hoàng)]

cho 1 vòng for chạy từ 0 đến vô cùng
trong vòng for đấy chạy thêm vòng for nữa duyệt mảng
nếu có p tử ở vòng for trên khác với phẩn tử ở vòng for dưới(trong mảng) break rồi in luôn

đấy là mình nghĩ thế chứ chưa thử

[Tuyen_Hoang (Tuyền Hoàng)]

#include"stdio.h"
int main()
{
	int i,n,t=0,a[100],j;
	printf("nhap n \n");scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		printf("a[%d]=",i);scanf("%d",&a[i]);
	}
	printf("mdso vua nhap\n");
	for(i=1;i<=n;i++)
		printf("%5d",a[i]);
	// ham duyet mang,tim phan tu khac mang nho nhat
	
	for(j=0;;j++){
		if(t==1) break;
		for(i=1;i<=n;i++)
			{if(a[i]>=0){
				if(a[i]!=j) {
					t=1;printf("\n%d",j);break;
					}
				}		
			}
}
}

[giang3 (Giang11)]

code của bạn với trường hợp -1 -2 -3 4 thì sẽ sai mất

[DoTran1]

-1 -2 -3 4 thì sẽ sai mất

Đã edit

if (a[0] > 1 || a[n-1] < 0){
  return result = 1;
}
for (i = 1; i < n - 1; i++){
   if (a[i] <= 0){
     if (a[i+1] <= 1) {
       continue;
     }
     else {
       return result = 1;
     }
   }
   else (a[i] + 1 < a[i + 1]) {
     return result = a[i] + 1;
   }
}
return result = (a[i] + 1);

[DoTran1]

Bạn thử làm vầy xem có nhanh hơn k?
Tạo ra mảng b chứa toàn bộ phần tử dương của mảng a (nguyên bản)

int j = -1;
for (int i = 0; i< n; i++){
	if(a[i] > 0){
		j++;
		b[j] = a[i];
	}
}
// Khong co a[i] > 0
if (j < 0){
	return result = 1;
}
//Sắp xếp mảng b tăng dần
//Duyệt để tìm result trên mảng b thôi