Tìm k phần tử gần nhất với giá trị cho trước

#1

các tiền bối cho e hướng đi của bài này, nếu k lẻ thì nó sẽ lấy về bên nào ạ, e nghĩ tính hiệu nào gần hơn thì sẽ gần hơn đúng ko ạ

image
image910×399 106 KB

1 Like
#2

Nếu không lẻ nó sẽ lấy về bên nào là thế nào ta :thinking:?

Anh nghĩ ra hướng rồi tại sao không thử code xem nào. Thực tế sẽ trả lời cho lí thuyết mà. :grinning:

5 Likes
#3

Gợi ý nho nhỏ ở câu đầu tiên trong đề: Cho mảng A gồm N phần tử đã được sắp xếp. Mà hình như đề lại không cho biết là các phần tử có được trùng nhau hay không, chắc là có rồi.

4 Likes
#4

Tức là nếu lấy 3 phần tử thì lấy 3 5 9 hay 5 9 11 :smiley:

5 Likes
#5

ban đầu e cũng có tham khảo: tìm kiếm tuyến tính cho k phần tử gần nhất.

  1. Bắt đầu từ phần tử đầu tiên và tìm kiếm điểm giao nhau (Điểm trước phần tử nào nhỏ hơn hoặc bằng X và sau phần tử nào lớn hơn). Bước này mất O (n) thời gian.
  2. Khi chúng ta tìm thấy điểm giao nhau, chúng ta có thể so sánh các phần tử ở cả hai phía của điểm giao nhau để in ra k phần tử gần nhất. Bước này mất O (k) thời gian.

Độ phức tạp về thời gian của lời giải trên là O (n).
e có code theo ý tưởng trên thì với test trong đề e sẽ in ra 23 và 11 chứ không phải 23 và 75 ạ nên e cũng chưa biết làm như nào cho đúng

3 Likes
#6

Dãy đã sắp xếp rồi bạn :smiley:

5 Likes
#7

thế giờ làm kiểu gì đây a

#8

Hi vodanh,
Cậu có thể share code của cậu được không? Sẽ hiệu quả hơn nếu bọn tớ biết cậu đã làm sai gì.

Regards,

2 Likes
#9

đây ạ:

1 Like
#10

Tớ hiểu rồi. Cậu bị confuse vì đề bài mâu thuẫn với test thôi :smiley:

Đề bài yêu cầu tìm K phần tử gần nhất của X trong mảng, và code của cậu đã làm theo ý tưởng đó.
Như cậu đã notice, test đưa ra kết quả là [23, 75], 2 số này không gần 24 hơn [23, 11], nên test trên mâu thuẫn với đề bài.

Giờ, tớ sẽ cho cậu 1 lời khuyên, cậu nên xác nhận lại yêu cầu và tính đúng đắn của đề bài lại với người ra đề, vì nó luôn luôn tốt khi cậu xác nhận lại ý hiểu của mình cho bất cứ 1 requirement nào, đặc biệt là những requirement cậu xác định được điểm bất hợp lý/mâu thuẫn/các corner case (như Nguyên và Rogp có chỉ ra).

Tớ đoán bọn tớ chỉ giúp cậu được tới đây thôi. Cậu thử xác nhận và nếu được, báo kết quả cho bọn tớ nhé! :smiley:
Hope it helps!

8 Likes
#11

Do dãy đã sắp xếp nên mảng gồm hai phần rõ rệt: a_i < x và a_i \geq x. Khi bạn kiểm tra giá trị ở chính giữa thì bạn có thể bỏ qua nửa mảng còn lại.

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