Tìm số lượng phần tử nhỏ nhất trong mảng cần xóa đi sao cho max(arr) - min(arr) <= k

duy_duy · June 25, 2021, 11:14pm

Cho một mảng arr và một số nguyên dương k . Tìm số lượng phần tử nhỏ nhất trong mảng cần xóa đi đi sao cho max(arr) - min(arr) <= k . Trong đó max(arr) và min(arr) lần lượt là phần tử lớn nhất và nhỏ nhất của mảng sau khi đã xóa đi các phần tử đó.
Ví dụ * Với arr = [1, 5, 6, 2, 8], k = 2 . Đầu ra minRemovals(arr, k) = 3.
Ông nào trùm thuật toán chỉ em hướng đi với ạ :((

Gio · June 25, 2021, 5:38pm

Thay vì tìm số phần tử bị xoá tối thiểu, sao không chuyển thành bài toán giữ lại số phần tử tối đa. Khi đó bạn chỉ cần tìm số phần tử a[i] đến a[i] + k. Đây là bài toán tìm kiếm nhị phân với a đã sắp xếp

kisuluoibieng · June 25, 2021, 5:41pm

Chuẩn men, binary search, với mỗi phần tử a[x] đã sắp xếp tăng dần, tìm y lớn nhất sao cho a[y] - a[x] <= k

duy_duy · June 25, 2021, 5:55pm

Cảm ơn các bác nhưng em vẫn không rõ y lắm…
em có làm qua binary search rồi nhưng mà vẫn mù mịt ý tưởng ạ :((

duy_duy · June 25, 2021, 5:56pm

mấy bác làm một ví dụ ngắn như ví dụ [1,5,7,8] k =3 được không ạ

rogp10 · June 26, 2021, 2:49am

Bạn dùng hai con trỏ left và right (ko phải int* đâu nhé, nó là chi tiết cài đặt )

Khởi tạo cả hai vào đầu mảng
Tăng right đến khi \Delta > k hay right vượt ra ngoài mảng (dùng binary search từ right đến end). Ghi nhận độ dài dãy ở đây.
Tăng left đến khi \Delta \leq k (dùng binary search từ left đến right)

duy_duy · June 26, 2021, 2:33am

dạ em cảm ơn bác nhiều ạ