Nhờ mọi người ý tưởng và thuật toán bài toán sau

[ngocvy]

Tại một điểm bán hàng tự động, mỗi loại hàng được gán tương ứng với một số nguyên dương gọi là mã hàng, hai loại hàng khác nhau có mã hàng khác nhau. Mỗi lần khách mua hàng, máy chỉ bán một lọai hàng với số lượng là 1 sản phẩm và ghi vào nhật ký của máy mã loại hàng đã bán. Sau khi kết thúc một đợt bán hàng, nhật kí bán hàng là một dãy số nguyên dương. Người quản lý cần thống kê xem loại hàng nào đã được máy bán nhiều nhất, số lượng hàng loại đó đã bán là bao nhiêu?
Dữ liệu vào: Dòng đầu tiên ghi số nguyên dương N (N<=10000) là số lượng hàng mà máy đã bán
N dòng tiếp theo mỗi dòng ghi một số nguyên dương là mã loại hàng đã bán trong nhật kí của máy. Giá trị các số nguyên dương không vượt quá 10^6.
Kết quả: mã loại hàng đã bán nhiều nhất và số lượng hàng loại đó mà máy đã bán.

n=11
1
2
2
3
2
4
5
2
6
7
6

Kết quả:

2 4

[rogp10]

Bài này lời giải bắt đầu bằng sort() nhưng có cách sort 1 phần cũng hay.

[Sherly1001]

Bài này cho vô map là được mà, sao phải sort vậy a.

[rogp10]

map thì phải tạo thêm cái map nữa để nhồi vào tốn mem.
Sort xong kéo 1 lần là ra.

[Sherly1001]

Nhưng sort xong lại mất công dò xem thằng nào nhiều nhất, ví dụ như case 10000 mã khác nhau thì lại phải lướt qua cả 10000 thằng, sort cho có màu.

[rogp10]

sort cho có màu

Vẫn hơn cấp phát cho std::map

[Sherly1001]

tìm max thì kéo 1 hơi là xong mà đâu cần quay lại

Đề nó kêu tìm thằng xuất hiện nhiều nhất và số lần xuất hiện mà a.

[rogp10]

Thì lưu thêm phần tử nào max, 1 slot mem

[Sherly1001]

Mà bài này cho có 10000 thằng, chắc sort cũng không lâu hơn bao nhiêu.

[rogp10]

Ừ nhỉ
Gọi A̅ là số phần tử khác nhau trong A (cardinality) thì:

• Nếu dùng std::map thì mem là O(A̅) và time là O(|A|logA̅) với một hằng số cũng khá lớn.
• Nếu dùng std::sort thì mem là O(log|A|) và time là O(|A|log|A|)
• Nếu dùng 3-way Quicksort thì mem là O(log|A̅|) và time là O(|A|logA̅)