Đề bài
Một mảng động như C++ std::vector lưu các phần tử của nó trong một khối bộ nhớ. Khi khối đó đầy và có một phần tử mới xuất hiện, nó sẽ cấp phát một khối lớn gấp đôi, sao chép các phần tử hiện có sang, rồi giải phóng khối cũ.
Bắt đầu với một mảng rỗng có dung lượng initial_capacity và chèn lần lượt pushes phần tử. Trước mỗi lần chèn, nếu size == capacity, hãy cấp phát lại: đếm một lần reallocation, cộng kích thước hiện tại vào số phần tử đã sao chép, và nhân đôi dung lượng.
Implement dynamic_array_growth(pushes, initial_capacity).
Input
pushes: Số phần tử được chèn.
initial_capacity: Dung lượng của mảng rỗng.
Output
Return [reallocations, copied_elements, final_capacity].
Ràng buộc
0 ≤ pushes ≤ 10^7
1 ≤ initial_capacity ≤ 10^6
Ví dụ
Đầu vào:
pushes = 5
initial_capacity = 1
Kết quả mong đợi:
expected = [3, 7, 8]Đầu vào:
long long pushes = 5;
long long initial_capacity = 1;
Kết quả mong đợi:
std::vector<long long> expected = {3, 7, 8};Đầu vào:
long pushes = 5;
long initial_capacity = 1;
Kết quả mong đợi:
long[] expected = new long[] {3, 7, 8};Giải thích
Dung lượng tăng 1 → 2 → 4 → 8 khi chèn phần tử thứ 2, thứ 3 và thứ 5, sao chép 1 + 2 + 4 = 7 phần tử: [3, 7, 8].
Đầu vào:
pushes = 4
initial_capacity = 4
Kết quả mong đợi:
expected = [0, 0, 4]Đầu vào:
long long pushes = 4;
long long initial_capacity = 4;
Kết quả mong đợi:
std::vector<long long> expected = {0, 0, 4};Đầu vào:
long pushes = 4;
long initial_capacity = 4;
Kết quả mong đợi:
long[] expected = new long[] {0, 0, 4};Giải thích
Bốn phần tử đều vừa trong khối đầu tiên, nên không có lần cấp phát lại nào: [0, 0, 4].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ cấp phát lại khi mảng đã đầy.
Gợi ý 2
Mỗi lần, mọi phần tử hiện có được sao chép và dung lượng tăng gấp đôi.
Gợi ý 3
Có thể nhảy từ lần gấp đôi này sang lần sau thay vì mô phỏng từng lần push.
Độ phức tạp mong đợi
thời gian O(log số lần push), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.