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

Mình nghĩ là đầu tiên thì nên sắp xếp cái mảng đó theo thứ tự từ nhỏ đến lớn.
Sau đó cho một vòng lặp chạy từ đầu đến cuối mảng đã sắp xếp, kiểm tra xem nếu phần tử trước cộng với 1 mà khác phần tử sau if (arr[i]+1)!=arr[i+1] thì sẽ trả về arr[i]+1 và break ra khỏi vòng lặp.

Cảm ơn thuật toán của bạn. hihi
Vậy trường hơp mình cho dãy int[] A = { -1,-2 }; thì output ra 0 hay mấy vậy bạn?

nếu vậy thì ta sẽ thêm điều kiện lớn hơn 0 cho arr[i+1].
if ((arr[i]+1)!=arr[i+1]) &&(arr[i]+1>0) và thêm return 1 ở sau vòng lặp.
khi nó chạy hết mảng mà không có giá trị nào được trả về thì sẽ trả về 1

Phải ra 1 chứ

Đúng ra là chạy thêm hai cái (while <= 0) nữa thì có khi được o(n) thu hẹp từ hai đầu.

Ra 1 vì đề yêu cầu >0 nhưng mà mình nghĩ bạn ấy nói vậy chỉnh xíu là được rồi

Mảng có phải sẽ gặp vấn đề khi int[] A = { 1, 3, 6, 4, 1, 2 }; không nhỉ? có 2 giá trị 1 thì lập tức return về 2 mất rồi hihi

Mình viết vầy thi test 3 trường hợp cho kết quả đúng, chưa biết t/h ngoại lệ nào để tes cho nó sai

public static int solution(int[] A) {
		int length = A.length;
		// find maximum
		int max = A[0];
		for (int i = 0; i < length; i++) {
			if (A[i] > max) {
				max = A[i];
			}
		}
		int i = 1;
		max = (max <= 0) ? 2 : max;
		while (i < max) {
			boolean isContain = false;
			for (int j = 0; j < length; j++) {
				if (i == A[j]) {
					isContain = true;
					break;
				}
			}
			if (!isContain) {
				return i;
			} else {
				i++;
			}
		}
		return ++max;
	}

Ban đầu mình cũng nghĩ là rà min nhưng nó là O(n^2) nên mình bỏ.

Cách của bạn là O(max*n), không hay đâu.

• Đầu tiên, vẫn phải sort lại mảng.

• Để ý tính chất sau:

  • Nếu số bé nhất mảng > 1 -> đáp số là 1.

  • Nếu số lớn nhất mảng < 1 -> đáp số là 1.

• Nếu 2 trường hợp trên không xảy ra, đến đây có 2 cách giải quyết:

  • for từ 1 đến số lớn nhất + 1 xem có số nào không thuộc mảng hay không. Kiểm tra 1 số có thuộc mảng hay không bằng cách tìm kiếm nhị phân. Độ phức tạp tổng là O(n log n + max(a[]) log n)

  • Dùng cách này, độ phức tạp tổng là O(n log n):

if ((arr[i]+1)!=arr[i+1]) &&(arr[i]+1>0)

Tuỳ bạn chọn.

for từ 1 đến số lớn nhất + 1 xem có số nào không thuộc mảng hay không.

Không cần thiết cứ bổ sung if(a[i] == a[i-1]) continue; thôi. Và câu lệnh này thể hiện rất rõ ý đồ của người viết.

Điều kiện > 0 của câu if có thể bỏ, vì ai giới hạn số for đâu

Ghi chú: @thớt

• Vòng lặp có hai câu break; là thoát vòng lặp ngay và continue; là chuyển qua lần lặp tiếp theo.
• Mảng tăng dần là một cấu trúc đặc biệt

Theo mình nghĩ là như thế này:
B1: Tạo 1 ArrayList rồi add tất cả phần tử trong list vào (Lọc luôn số âm)
B2: Chạy 1 hàm for từ đầu đến cuối ArrayList đó, xong dùng luôn hàm .contains() của ArrayList luôn
B3: Nếu là Failse thì sẽ là số cần tìm.
B4; Với thuật toán này sẽ có 2 số hợp lệ, thì lấy số bé hơn

Mảng có n phần tử thì tối đa cũng chỉ chứa được n số nguyên dương liên tiếp -> như vậy kết quả thuộc [1,n+1]

Dùng 1 mảng đánh dấu kiểm tra những số nào có trong khoảng đó, sau đó tìm số nhỏ nhất chưa được đánh dấu.

public class A{

    public static int search(int [] a) {
        int n = a.length;
        boolean mark[] = new boolean[n+2];
        for(int i=0;i<n;i++) {
            if(a[i]<=0||a[i]>n+1) continue;
            mark[a[i]] = true;
        }
        for(int i=1;i<mark.length;i++) {
            if(!mark[i]) return i;
        }
        return 0;
    }
    public static void main(String [] args) {
        int a[] = new int[]{1,3,6,4,5,2};
        System.out.println(search(a));
    }
}

Thì đáp số là số 1 .

Oh :(( Mình nhầm là trong khoảng các số ở mảng xin lỗi bạn

Thật ra bài này làm đc trong O(N) với N ~ 1e6 bằng cách dùng mảng đánh dấu những phần tử dương <= N xuất hiện trong bảng, dễ chứng minh chắc chắn sẽ có số nguyên dương trong [1,N+1] chưa xuất hiện trong mảng.
À anh gió chứng minh rồi :v

Tạo mảng boolean n phần tử, n là số phần tử lớn nhất. Rồi for hết mảng nta cho. Mỗi vong for gặp số nào >0 thì A[i]= true. Rồi for mảng A . Tìm giá trị false đầu tiên .in nó ra là đc. 2 vòng lặp đơn là xong.

Cách của bạn chính là cách của bạn @Gio rồi.

Đây là cách mà mình làm :)) thấy vẫn chưa tối ưu lắm :))

    public static  int find(Integer[] a)
    {
        int out = 1;
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i : a)
        {
            if(i >= 0)
            {
                arr.add(i);
            }
        }
        for(int i = 0; i < arr.size(); i++)
        {
            int next = arr.get(i) + 1;
            if(!arr.contains(next))
            {
                if(out > next || next == 2)
                {
                    out = next;
                }
            }
        }
        return out;
    } 

Bài cũng hay :D, lâu lâu code thử tí, không biết đúng yêu cầu chưa.

public class Main {
    public static void main(String... args) {
        test(new int[] {1, 3, 6, 4, 1, 2}, 5);
        test(new int[] {}, -1);
        test(new int[] {1}, 2);
        test(new int[] {2}, 1);
        test(new int[] {6}, 1);
        test(new int[] {-1, 0, -2 ,5, 1}, 2);
    }

    public static void test(final int[] input, final int expected) {
        if(findMin(input) == expected) {
            System.out.println("PASS");
        } else {
            System.out.println("FAIL: findMin() = " + findMin(input));
        }
    }

    public static int findMin(final int[] input) {
        if(input.length < 1) return -1;

        if(input.length == 1) {
            if(input[0] == 1) return 2;
            else return 1;
        }

        int[] t = new int[input.length];

        for(int i : input) {
            if(i > 0) t[i - 1] = 1;
        }

        int gotcha = 1;
        for(int i = 0; i < t.length; i++) {
            if(t[i] == 0) {
                gotcha = i + 1;
                break;
            }
        }

        return gotcha;
    }
}

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