Đố fun - tìm phần tử nhỏ thứ n trong array (không sort)

#21

unordered_set/unordered_map có thứ tự đâu, làm sao biết phần tử nào lớn nhất mà remove? Phải tìm phần tử lớn nhất trong hashset mỗi lần remove thì tốn O(n) tìm kiếm cho 1 lần remove, ~O(n^2) lần tổng cộng rồi.

dễ ăn thế thì đâu có thuật toán kia :smile:

1 Like
#22

á nhầm, sorry @@~
quên mất nó lưu theo hash @@~

#24

ý tưởng của em là sắp xếp thành 1 dãy tăng dần r gọi phần tử thứ m ra. hoặc dãy giảm dần rồi gọi phần tử thứ n - m + 1 ra. liệu cách này có tối ưu không ạ ?

#25

Đề bài yêu cầu là không sử dụng sắp xếp nhé bạn

#26

Dùng 1 mảng đánh dấu, tìm max-min rồi chạy từ min -> max đếm đủ n ô đã đánh dấu thì xuất ra vị trí có được tính là sắp xếp không nhỉ ? :smiley:

#27

Mình dùng c# thì như này có đúng ko nhỉ?

Int[] bố = (1,2,…,m);
Int thang_con_can_tim ;
Int minCount =1;
If (n<=m)
{
Foreach (con in bố, i =0, i<m, i++)
{
For (y=0, y<m, y++){
If(con[i] > con[y]){
minCount++
}
If(minCount = n){
thang_con_can_tim = con[i]
}
}
}
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?