chào mọi người, em có câu muốn hỏi ạ:
cho 1 tập các phần tử số nguyên gồm n ptu (các phần tử có thể lặp lại). tìm thuật toán tìm và đưa ra dãy con các phần tử sắp xếp k giảm, tối đa 3 số khác nhau trong dãy, có độ dài lớn nhất.
ví dụ: 111222233456666 là tập n ptu sau khi săp xếp, thì tập in ra phải là: 111222233
Thuật toán giải với O(n)
Ý tưởng:
- Duyệt mảng 1 lần để lưu thông tin của tất cả dãy con trong chuỗi (ràng buộc theo đề bài), lưu từng thông tin vào 1 mảng khác;
- Duyệt mảng thông tin đó và chọn ra thông tin thể hiện dãy con dài nhất.
Cả 2 cái, mỗi cái duyệt 1 lần, gần với O(n), có thể vừa làm điều 1 vừa làm điều 2 cùng một lúc và ko cần thêm mảng nào cả, đúng O(n).
1 Like
Cái này dùng thử HashMap đi. Rồi dùng môt flag để check 3 lần.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?