Tìm phần tử cân bằng của một mảng
[Tác giả: Navtosh
Ngày xuất bản: 04/06/2020
Link: https://link.medium.com/RqwJVgSpI7]
(ND: Equilibrium index, trong bài này mình xin phép dịch thô thiển là phần tử cân bằng)
Độ khó: Trung bình
Thường được hỏi tại: Amazon, Adobe, Hike
Ba phương án được đề xuất:
- Tiếp cận trực tiếp (dùng 2 vòng lặp lồng nhau)
- Sử dụng thêm bộ nhớ (mảng Prefix sum)
- Sử dụng Single Scan
Những điều bạn học được qua bài viết này:
Đây là một câu hỏi thú vị trong phỏng vấn, giúp bạn hiểu được việc tối ưu bộ nhớ và giải quyết bài toán với single scan. Những bài toán tương tự như này thường được hỏi rất nhiều trong các buổi phỏng vấn đó nhé.
Viết một chương trình tìm chỉ số của phần tử cân bằng của một mảng. Phần tử cân bằng của một mảng là phần tử mà tổng các phần tử đứng trước nó bằng tổng các phần tử đứng sau nó. (Ảnh 0)
Ý tưởng
Phương pháp tiếp cận trực tiếp này sử dụng 2 vòng lặp lồng nhau. Vòng lặp bên ngoài chạy từng phần tử của mảng, ở mỗi phần tử ta dùng tiếp một vòng lặp để tính tổng trái và tổng phải, rồi so sánh với nhau, kiểm tra xem có phần tử cân bằng hay không.
Code C++ (Ảnh 1)
Đánh giá độ phức tạp thuật toán
Độ phức tạp thời gian: O(n^2)
Độ phức tạp bộ nhớ: O(1)
Ý tưởng
Ta sẽ sử dụng một mảng prefixSum cũng gồm n phần tử, trong đó phần tử thứ i của prefixSum lưu tổng các giá trị từ đầu mảng đến phần tử thứ i trong mảng gốc.
leftSum gán bằng 0, rightSum gán bằng prefixSum[n-1]
Sau đó, chạy một vòng lặp, mỗi lần lặp ta lại trừ rightSum đi một lượng a[i], đồng thời gán leftSum mới bằng prefix[i-1]. Nếu leftSum = rightSum, trả về chỉ số i.
Code C++ (Ảnh 2)
Đánh giá độ phức tạp thuật toán
Độ phức tạp thời gian: O(n)
Độ phức tạp bộ nhớ: O(n)
cách 3 – sử dụng thuật toán single scan
Ý tưởng
Ta sẽ tính tổng của cả mảng trước. Điểm khác biệt với cách 2 là ở cách 3 này, ta không lưu mảng prefixSum nữa. Thay vào đó, ta cập nhật leftSum và rightSum lần lượt trong từng bước lặp, cụ thể:
rightSum = rightSum – a[i] (ban đầu rightSum = totalSum)
Tiếp đó, ta so sánh leftSum và rightSum và trả về chỉ số i. Nếu không thoả mãn, ta tiếp tục:
leftSum = leftSum + a[i] (ban đầu leftSum = 0)
và chuyển đến vòng lặp tiếp theo.
Code C++ (Ảnh 3)
Đánh giá độ phức tạp thuật toán
Độ phức tạp thời gian: O(n)
Độ phức tạp bộ nhớ: O(1)
—-
Các câu hỏi mà nhà tuyển dụng có thể hỏi thêm:
- Có thể dùng bảng băm để giải bài toán này không?
- Có trường hợp đặc biệt nào không?
Các bài toán khác giúp thực hành thuật toán single scan
- Loại bỏ các phần tử trùng lặp trong mảng
- Bài toán chia sô cô la
- Sắp xếp mảng tăng giảm xen kẽ
- Đếm số mảng con có tổng chẵn
- v.v…
(ND: Các bạn có thể vào bài viết gốc để xem rất nhiều các bài toán tác giả liệt kê, có link leetcode hoặc geeksforgeeks)
Chăm cày thuật toán bạn nhớ!
