[Hỏi] Cho 1 mảng n phần tử, tìm phần tử nguyên dương nhỏ nhất ko chứa trong mảng đó

greans

New Member
Joined
Sep 27, 2017
Messages
1,711
Reaction score
0
Half-Blood Prince said:
Đây cách em tôi bảo đây.
Mấy ông trên quăng gạch ghê quá nên code vậy.
Solution dùng couting sort, độ phức tạp O(N) O(L) với L là giới hạn giá trị của phần tử trong mảng.
Ví dụ giới hạn giá trị từ 0 - 10000.

Code: class HelloCodiva { //Đầu bài mảng N phần tử, giá trị mỗi phần tử trong khoảng từ 1 đến 10000 = L static int L = 10000; public static void main(String[] args) { int[] array1 = {1, 2, 3, 4}; int[] array2 = {1, 3, 4, 5, 6, 9}; int[] array3 = {2, 4, 8, 9, 3}; System.out.println(findMin(array1)); System.out.println(findMin(array2)); System.out.println(findMin(array3)); } //counting sort public static int findMin(int[] array){ int[] count = new int[L 1]; for(int i = 0; i < array.length; i ){ count[array] ; } for(int i = 1; i <= L; i ){ if(count == 0){ return i; } } return L 1; } } Code: 5 2 1 Completed with exit code: 0
Tìm max cho rồi, đỡ phải set cái restriction :) vẫn ko thay đổi complexity
 

Kurisu Makise

New Member
Joined
Sep 27, 2017
Messages
698
Reaction score
0
Gray_Fullbuster said:
1 vòng for thì tốn bộ nhớ
let values =[]
for( let i=0; i<n; i ){
values[array] = true
}

index đầu tiên trong values có giá trị bằng flase là kết quả cần tìm
Tính cái false đó cần thêm 1 vòng for phụ nữa :D
Mà bạn quên kiểm tra phần tử có > 0 hay chưa chứ index là phải > 0 mới ổn nhé :D
 

gnoLuV

New Member
Joined
Sep 28, 2017
Messages
134
Reaction score
0
dung bang bam nhe ban. bang bam chua n phan tu tu 1 den n sau do duyet lai bang bam tim phan tu dau tien bi thieu la dc
 

talaai1312_ver2

New Member
Joined
Oct 10, 2017
Messages
676
Reaction score
0
int max = array[1];

int find = 0;

for (int i = 1; i < array.Length(); i++)

{

// Tìm max

if(array > max)

max = array;

// Tìm index (nếu ko có thì index < 0)

int index = array.IndexOf(array, i)

if (index < 0) find = i, break

}



if (find = 0) find = max + 1

else return find
 

oORouter

New Member
Joined
Dec 9, 2017
Messages
12
Reaction score
0
Giả thiết mảng là dãy nguyên dương ( Nếu là mảng nguyên thì thay đổi chút).



B1. Tìm ra phần tử nhỏ nhất của mảng: amin. Chi phí O(n) (Dùng kiểu nổi bọt)

B2. If amin > `1: return 1.

else // amin == 1

Cách 1. Quicksort, xong chạy code Nhaozo. Chi phí O(nlogn).

Cách 2. CurrentMin = 1

for k in 2 ... n:

Tìm phần tử nhỏ thứ k (ak). chi phí O(n-k).

If ak = currentMin +1 :

currentMin = ak

continue

else if ak == currentMin:

continue

else:

return currentMin + 1

//Chi phí A



Xác suất để một dãy số không chứa 1 là: p = (1/(MAX_INT-1)^N.

Độ phức tạp trung bình pO(n) + (1-p)O(A)
 

**Doremon**

New Member
Joined
Sep 27, 2017
Messages
3,004
Reaction score
2
Gray_Fullbuster said:
1 vòng for thì tốn bộ nhớ
let values =[]
for( let i=0; i<n; i ){
values[array] = true
}

index đầu tiên trong values có giá trị bằng flase là kết quả cần tìm
n là giá trị lớn nhất trong mảng phải ko bác , nếu thế thì bác cũng phải mất 1 for để tìm nó chứ :surrender: mà space cao quá nên e nghĩ chắc ko ổn :D hơn nữa cách này nhiều lỗ hổng quá
Sent from SKII using vozFApp
 

greans

New Member
Joined
Sep 27, 2017
Messages
1,711
Reaction score
0
Code:

int max = array[1];
int find = 0;
for (int i = 1; i < array.Length(); i++)
{
// Tìm max
if(array > max)
max = array;
// Tìm index (nếu ko có thì index < 0)
int index = array.IndexOf(array, i)
if (index < 0) find = i, break
}

if (find = 0) find = max + 1
else return find


1 vòng for của thớt nè, chỉ có là O(n^2)
 

lovesick00

New Member
Joined
Jun 27, 2019
Messages
142
Reaction score
0
Mình nghĩ như nhiều bác ở đây nghĩ, là độ phức tạp tính toán (complexity) của bài toán là O(n), tức là dùng nhiều for đơn, ko có for lồng, chứ 1 for theo nghĩa đen thì gần như ko thể rồi
 
Top