[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
lovesick00 said:
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
có lẽ thế, hoặc bạn thớt đố mẹo cl gì đấy. đỉnh cao của bài này là O(n) với space complexity O(1) rồi
 

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
 

Gray_Fullbuster

New Member
Joined
Oct 9, 2017
Messages
83
Reaction score
0
với 0 < n <= 10^6
thì cách này chạy dưới 1s đủ để pass qua tất cả các testcases

theo cách mình hiểu 1 vòng for tức là O(n)
dùng 1 vòng for nhưng trong đó if else tính toán quá nhiều thì có khi còn chậm hơn 2 vòng for tách biệt đơn giản nữa


**Doremon** said:
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

Sent from SKII using vozFApp
 

spam102

New Member
Joined
Sep 28, 2017
Messages
337
Reaction score
0
Được xài hàm native hem?
Js array include là đúng 1 vòng for luôn. Cho chạy từ 1 đến length +1
Nếu array include(i) false thì trả về i là dc

Gửi từ Samsung SM-N950F bằng vozFApp
 

Half-Blood Prince

New Member
Joined
Sep 28, 2017
Messages
88
Reaction score
0
greans said:
vấn đề là complexity ko thay đổi
Em biết mà, nhưng ông thớt với mấy ông kia đòi 1 vòng for O(n) thì em bó tay đợi đáp án thôi :pudency:
 

phuongbkhn

New Member
Joined
Sep 29, 2017
Messages
534
Reaction score
0
e mới học Python, viết cái code này thấy đơn giản mà ok, các thím check giúp em xem với :D

A = [2,2,1,3,60,5]

i = 1
while i in A:
i = 1

else:
print(i)
 

uyenly

New Member
Joined
Aug 20, 2019
Messages
146
Reaction score
0
phuongbkhn said:
e mới học Python, viết cái code này thấy đơn giản mà ok, các thím check giúp em xem với :D



Image
Mình nghĩ là ở chỗ "i in A" được tính là một vòng lặp rồi bạn :chaymau: cộng thêm vòng while là nó thành 2 vòng rồi
 

DuaHau'

New Member
Joined
Sep 29, 2017
Messages
389
Reaction score
0
Idea của mình là check 4 cái, dùng for() quét hết mảng:

1. dùng 1 cờ lưu lại check xem có số 1 trong mảng không;

2. dùng 1 biến để tìm và lưu lại phần tử lớn nhất trong mảng ==> max

3. tìm số nhỏ nhất nằm giữa 2 phần tử cạnh nhau trong mỗi 3 phần tử liên tiếp:

Ví dụ ở step 3: cho mảng {1, 4, 8, 9}:

- so sánh [1,4] => 2 và [4,8] => 5

===> 2 < 5, giữ 2 lại,

- tìm số nhỏ nhất không có mặt của [8,9]==> 7

==> 2 < 7, giữ 2 lại

và cứ vậy



4. Sau khi rởi khỏi For()

4.1 check step1, nếu không có 1 trong mảng thì return 1;

else

4.2 so sánh output ở step3 với giá trị (max+1) ở step2. rồi return cái nào nhỏ hơn.



p/s: step 3 có vẻ không ổn lắm
 

phuongbkhn

New Member
Joined
Sep 29, 2017
Messages
534
Reaction score
0
uyenly said:
Mình nghĩ là ở chỗ "i in A" được tính là một vòng lặp rồi bạn :chaymau: cộng thêm vòng while là nó thành 2 vòng rồi
"while i in A" thì là 1 chứ thím :D
 
Top