Tìm số nguyên dương nhỏ nhất > 0 không chứa trong mảng đã cho
ví dụ cho mảng int[] A = { 1, 3, 6, 4, 1, 2 }; thì phải ouput ra số 5
Mình không thông minh nên chỉ nghĩ được là sẽ chạy số n từ 1 đến số lớn nhất của mảng, lặp vòng for xem con số n đó có bằng với phần tử trong mảng hay không, nếu mà bằng thì break, còn không thì in ra số đó.
Như vậy có đúng ko ạ, ai có thể chia sẻ cho mình thuật toán khác với được không ạ.
Xin cảm ơn.
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):
Tuỳ bạn chọn.
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
break; là thoát vòng lặp ngay và continue; là chuyển qua lần lặp tiếp theo.
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;
}
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?