Find Pivot Index

Q: Độ phức tạp thời gian của Find Pivot Index là bao nhiêu?

Lời giải dùng tổng và tổng tích lũy chạy trong thời gian O(n) , với một lượt để cộng các phần tử trong mảng và một lượt để quét mảng, cùng với O(1) bộ nhớ bổ sung. Tính lại cả hai phía ở mỗi chỉ số sẽ mất O(n²) .

DễTổng tiền tố

+10

Bạn nhận được một mảng số nguyên nums. Chỉ số trục là chỉ số mà tổng các giá trị ở bên trái bằng tổng các giá trị ở bên phải. Giá trị tại chính trục không thuộc bên nào, và tổng của một bên không có giá trị nào là 0.

Trả về chỉ số trục ngoài cùng bên trái, hoặc -1 nếu không có chỉ số nào là trục.

Hàm

pivotIndex(nums: integer-array) → integer

numsinteger-array: mảng số nguyên cần cân bằng
Trả vềinteger: chỉ số trục nằm ngoài cùng bên trái, hoặc -1 nếu không có

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Ví dụ

Đầu vào: nums = [3, 1, 5, 2, 2]
Đầu ra: 2
Giải thích: Tại chỉ số 2, tổng bên trái 3 + 1 = 4 cân bằng với tổng bên phải 2 + 2 = 4. Chỉ số 0 cho kết quả 0 so với 10, còn chỉ số 1 cho kết quả 3 so với 9, vì vậy 2 là điểm trụ ngoài cùng bên trái.

Đầu vào: nums = [1, 2, 3]
Đầu ra: -1
Giải thích: Ba ứng viên lần lượt có điểm 0 đấu với 5, 1 đấu với 3 và 3 đấu với 0. Không có chỉ số nào cân bằng, nên đáp án là -1.

Câu hỏi mở rộng

Bạn có thể tìm trục phân vùng ngoài cùng bên trái bằng cách chỉ đọc mỗi giá trị một lần mà không tính tổng trước không? Cách đó tốn bao nhiêu bộ nhớ?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Tính lại cả hai tổng tại mỗi chỉ số sẽ tốn O(n²). Tổng bên trái tăng thêm một giá trị sau mỗi bước, còn tổng bên phải là phần còn lại của tổng tất cả. Vì vậy, một lượt duyệt để tính tổng tất cả và một lượt duyệt với tổng bên trái được cập nhật liên tục sẽ tìm ra điểm trục ở bên trái nhất, chỉ cần lưu hai số trong bộ nhớ.

Cộng hai vế tại mỗi chỉ số

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi chỉ số, hãy cộng các giá trị đứng trước và các giá trị đứng sau chỉ số đó, rồi so sánh hai tổng. Thử các chỉ số từ trái sang phải sẽ giúp bạn tìm được điểm xoay khớp đầu tiên ở vị trí ngoài cùng bên trái. Ở mỗi đầu, một vòng lặp chạy 0 lần và tổng của nó vẫn là 0, đó là lý do [4, -4, 9] trả về 2.

Mỗi chỉ số cộng n-1 giá trị còn lại. Với 10,000 giá trị, phép tính này cần gần 100 triệu phép cộng, phần lớn trong số đó lặp lại các tổng đã tính từ chỉ số trước.

Thuật toán

Lặp i qua mọi chỉ số của nums.
Cộng các giá trị từ nums[0] đến nums[i-1] để tính tổng bên trái.
Cộng các giá trị từ nums[i+1] đến giá trị cuối cùng để tính tổng bên phải.
Nếu hai tổng bằng nhau, trả về i.
Nếu không có chỉ số nào phù hợp, trả về -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Mảng tổng tiền tố

Ý tưởng

Mảng tổng tiền tố (prefix sum array) tính tổng một lần. Gọi prefix[k] là tổng của k giá trị đầu tiên, với prefix[0] = 0; với [3, 1, 5, 2, 2], ta có [0, 3, 4, 9, 11, 13]. Tổng bên trái chỉ số i là prefix[i], còn tổng bên phải là prefix[n] - prefix[i+1]. Tại chỉ số 2, ta có 4 và 13 - 9 = 4, vậy đây là một điểm trục.

Chỉ cần duyệt một lượt để tạo mảng, và mỗi lần kiểm tra mất thời gian hằng số: độ phức tạp thời gian O(n), cùng n+1 số bổ sung trong bộ nhớ.

Thuật toán

Tạo prefix có độ dài n+1 với prefix[0] = 0.
Điền mảng: prefix[k+1] = prefix[k] + nums[k].
Với mỗi chỉ số i, lấy tổng bên trái là prefix[i] và tổng bên phải là prefix[n] - prefix[i+1].
Trả về i đầu tiên có hai tổng bằng nhau, hoặc -1 sau vòng lặp.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Tổng cộng và tổng lũy kế bên trái

Ý tưởng

Tại chỉ số i, cách tiếp cận dùng tổng tiền tố đọc prefix[i], prefix[i+1] và prefix[n]. Giá trị cuối cùng là tổng, không bao giờ thay đổi, còn hai giá trị kia là tổng lũy kế mà bạn có thể tính khi duyệt qua mảng. Vì vậy, hãy giữ tổng và một tổng bên trái thay vì mảng.

Mỗi giá trị nằm bên trái i, tại i hoặc bên phải i, nên tổng bên phải là total - left - nums[i]. Hãy so sánh trước khi cộng nums[i] vào left, để tổng bên trái không bao giờ bao gồm giá trị bạn đang kiểm tra. Trong ví dụ đầu tiên, tổng là 13, và chỉ số 2 cho kết quả 4, bằng với 13 - 4 - 5 = 4.

Duyệt hai lượt mất thời gian O(n), còn hai số chỉ cần không gian O(1).

Thuật toán

Cộng tất cả giá trị vào total.
Đặt left thành 0.
Với mỗi chỉ số i, nếu left bằng total - left - nums[i], trả về i.
Nếu không, cộng nums[i] vào left rồi tiếp tục.
Nếu vòng lặp kết thúc, trả về -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Lỗi thường gặp và trường hợp biên

Cộng nums[i] vào tổng bên trái trước khi so sánh. Khi đó, phía bên trái bao gồm giá trị tại điểm xoay, nên [3, 1, 5, 2, 2] không còn tìm thấy chỉ số 2.
Tính phía bên phải bằng total - left. Cách này tính nums[i] vào phía bên phải; hãy trừ giá trị đó đi.
Bỏ qua chỉ số 0 hoặc chỉ số cuối cùng. Tổng của một phía rỗng bằng 0, nên [1, -1, 1] trả về 0 và [4, -4, 9] trả về 2.
Trả về kết quả khớp cuối cùng. Trong [0, 0, 0], mọi chỉ số đều cân bằng và đáp án là 0.
Quên rằng mảng trong Lua và R bắt đầu từ 1. Trả về i-1 để đáp án là chỉ số bắt đầu từ 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Find Pivot Index là bao nhiêu?

Lời giải dùng tổng và tổng tích lũy chạy trong thời gian O(n), với một lượt để cộng các phần tử trong mảng và một lượt để quét mảng, cùng với O(1) bộ nhớ bổ sung. Tính lại cả hai phía ở mỗi chỉ số sẽ mất O(n²).

Có thể giải Find Pivot Index bằng hai con trỏ không?

Không đáng tin cậy. Cách quét từ hai đầu và luôn mở rộng phía nhỏ hơn giả định rằng thêm một giá trị sẽ làm một phía lớn hơn. Các giá trị ở đây có thể xuống đến -1000, nên một phía có thể thu nhỏ khi được mở rộng, khiến các con trỏ vượt qua điểm trục thực tế.

Chỉ số trục của mảng có một phần tử là bao nhiêu?

Kết quả là 0. Hai phía của phần tử duy nhất đều trống, và tổng của một phía trống bằng 0, nên hai phía bằng nhau. Lời giải dùng tổng tích lũy trả về 0 ở lần so sánh đầu tiên.

def pivotIndex(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 1, 5, 2, 2]

Đầu ra mong đợi

Find Pivot Index

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Cộng hai vế tại mỗi chỉ số

Mảng tổng tiền tố

Tổng cộng và tổng lũy kế bên trái

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự