Tìm số tự nhiên nhỏ nhất không xuất hiện trong mảng

#1

BT: Cho dãy gồm N ( N <= 30000 ) số tự nhiên không vượt quá 10^9, tìm số tự nhiên nhỏ nhất không xuất hiện trong dãy.
Cho mình xin cái thuật toán luôn nhé.

#2

thuật toán là gì?

bạn tự cho 1 dãy số rồi tự giải ra đáp án xem? bạn giải như thế nào?

2 Likes
#3

Screenshot 2020-12-01 123746
Screenshot 2020-12-01 1237461695×636 20.8 KB

Mình làm như này mà thử lại thì thấy sai
Mình muốn hỏi các bước làm á

#4

bạn có biết giải bài này chưa?

1000 300 450 3 90 2 1 5

vậy với dãy trên thì đáp án là gì? giải như thế nào?

1 Like
#5

mình không biết nên mới hỏi :<

#6

Trong dãy số này:

1000 300 450 3 90 2 1 5

Số nào là số tự nhiên bé nhất không xuất hiện trong mảng này vậy? Vì sao cậu biết?

3 Likes
#7
  1. Bạn sắp xếp dãy đi đã rồi nhìn vào dãy sau khi sắp xếp là xong
1 Like
#8

bạn không biết làm thì viết code làm gì?
đọc đề xong cứ code đại rồi sửa sửa là sẽ ra được đáp án sao?

Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a specific task

bạn không biết bạn cần làm gì thì làm sao mô tả cho máy tính chạy?

4 Likes
#9

Chả hiểu kiểu gì …?

3 Likes
#11 
:-> numbers[1..N]: int[]
<- int
return 0 if numbers.empty? || min(numbers) != 0 // đk đề bài
numbers.sort()
//đk đề bài
last_seen := 0
for_each number in numbers:
   return last_seen + 1 if number > last_seen + 1
   last_seen = number
return last_seen + 1
1 Like
#12

Không biết do bạn sai đề hay do mình mới dậy nhỉ " tìm số tự nhiên nhỏ nhất không xuất hiện trong dãy" không xuất hiện thì sao tìm ???

2 Likes
#13

mình chỉ nghĩ được giải thuật đơn giản thế này thôi:

Sắp xếp dãy theo thứ tự từ bé đến lớn.

Duyệt từ phần tử bé nhất của dãy đến khi tìm được số tự nhiên cần tìm.

Độ phức tạp của thuật toán là 2N.

Thanks

1 Like
#14

Mình lấy ví dụ này cho dễ hiểu nhé:
Trong mảng 0; 1; 2; 4; 6

Thì số tự nhiên nhỏ nhất không xuất hiện trong dãy là 3

2 Likes
#16

Đã sắp xếp thì là O(NlogN) rồi mà ta? :stuck_out_tongue:

Bài này có thể tính ở O(N) bằng cách dùng HashSet.

2 Likes
#17

Chi tiết hơn đi bạn. Mình vẫn chưa hình dung ra

#18

Đại khái thì là vầy:

h = set(numbers)
i = 0
while i in h: i+=1
return i
3 Likes
#19

Ngắn gọn đơn giản dễ hiểu nhỉ.
1 Like

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?