Summary Ranges

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

O(n) . Mỗi giá trị được duyệt một lần và mỗi khoảng được ghi một lần. Ngoài danh sách đầu ra, không gian phụ là O(1) : điểm bắt đầu của khoảng hiện tại và một hoặc hai chỉ số.

DễKhoảng Mảng và chuỗi

+10

Bạn nhận được một mảng nums gồm các số nguyên phân biệt, đã được sắp xếp. Hãy chia mảng thành ít khoảng liên tiếp nhất có thể, sao cho mỗi giá trị thuộc đúng một khoảng. Viết khoảng a..b dưới dạng văn bản "a->b", hoặc dưới dạng "a" nếu khoảng đó chỉ có một giá trị. Trả về các khoảng theo thứ tự tăng dần.

Hàm

summaryRanges(nums: integer-array) → string-array

numsinteger-array: mảng số nguyên phân biệt đã sắp xếp
Trả vềstring-array: các khoảng giá trị dưới dạng văn bản, từ giá trị nhỏ nhất đến lớn nhất

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums được sắp xếp theo thứ tự tăng dần và không có phần tử trùng lặp.

Ví dụ

Đầu vào: nums = [0, 1, 2, 5, 6, 9]
Đầu ra: ["0->2", "5->6", "9"]
Giải thích: 0, 1, 2 nối tiếp nhau, nên chúng tạo thành "0->2". Bước nhảy từ 2 đến 5 bắt đầu một khoảng mới, "5->6", còn 9 đứng riêng thành "9".

Đầu vào: nums = [-3, -1, 0, 1, 4, 7, 8]
Đầu ra: ["-3", "-1->1", "4", "7->8"]
Giải thích: -3 không có số liền kề (-2 bị thiếu), -1, 0, 1 tạo thành một dãy liên tiếp, 4 đứng riêng lẻ và 7, 8 kết thúc danh sách. Các giá trị âm cũng hoạt động theo cách tương tự: sau -1 là -1 + 1 = 0.

Câu hỏi mở rộng

Giả sử nums có thể chứa các giá trị trùng lặp, như [1, 2, 2, 3]. Bạn sẽ thay đổi gì để chương trình vẫn in ra "1->3"?

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

Vì các giá trị đã được sắp xếp và không trùng nhau, một khoảng gồm các số nguyên liên tiếp là một dãy các phần tử kề nhau trong mảng (array), và dãy kết thúc đúng tại vị trí hai phần tử kề nhau chênh lệch hơn 1. Không khoảng nào có thể vượt qua khoảng trống như vậy, nên cắt tại mọi khoảng trống sẽ tạo ra số khoảng ít nhất.

Kiểm tra cả hai giá trị liền kề của mỗi giá trị

Ý tưởng

Một khoảng bắt đầu tại giá trị đầu tiên hoặc tại giá trị có phần tử liền trước không nhỏ hơn nó một đơn vị. Khoảng kết thúc tại giá trị cuối cùng hoặc tại giá trị có phần tử liền sau không lớn hơn nó một đơn vị. Trong [0, 1, 2, 5, 6, 9], các khoảng bắt đầu tại 0, 5 và 9, rồi kết thúc tại 2, 6 và 9.

Hãy ghi nhớ giá trị nơi khoảng hiện tại bắt đầu. Khi khoảng kết thúc tại nums[i], hãy ghi "start->nums[i]", hoặc chỉ ghi "start" nếu khoảng bắt đầu và kết thúc tại cùng một giá trị, như trường hợp của 9.

Mỗi giá trị chỉ xét hai phần tử liền kề một lần: thời gian O(n) và chỉ cần ghi nhớ một giá trị bắt đầu, nên dùng thêm O(1) không gian.

Thuật toán

Đặt start = nums[0].
Với mỗi chỉ số i: nếu i > 0 và nums[i] != nums[i-1] + 1, đặt start = nums[i].
Nếu i là chỉ số cuối cùng hoặc nums[i+1] != nums[i] + 1, phạm vi kết thúc tại đây.
Thêm "start" nếu start == nums[i], nếu không thì thêm "start->nums[i]".
Trả về danh sách sau chỉ số cuối cùng.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Hai con trỏ trên mỗi đoạn liên tiếp

Ý tưởng

Tìm hai đầu mút của mỗi đoạn. Con trỏ i đứng tại giá trị đầu tiên. Con trỏ j bắt đầu từ i và di chuyển sang phải khi giá trị tiếp theo lớn hơn đúng một đơn vị, nên nó dừng tại giá trị cuối cùng. Sau đó, i nhảy đến j+1.

Với [-3, -1, 0, 1, 4, 7, 8]: tại -3, giá trị tiếp theo -1 không phải là -2, nên "-3" đứng riêng. Từ -1, j đi qua 0 và 1 rồi dừng trước 4: "-1->1". Tiếp theo là "4" và "7->8".

Cả hai con trỏ chỉ di chuyển về phía trước, nên vòng lặp bên trong chạy tổng cộng n lần: độ phức tạp thời gian O(n) và bộ nhớ phụ O(1).

Thuật toán

Đặt i = 0.
Đặt j = i, rồi di chuyển j sang phải khi j+1 < n và nums[j+1] == nums[j] + 1.
Thêm "nums[i]" nếu i == j, nếu không thì thêm "nums[i]->nums[j]".
Đặt i = j + 1 và lặp lại cho đến khi i vượt quá phần tử cuối.
Trả về danh sách.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

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

Quên khoảng cuối cùng. Vòng lặp chỉ ghi một khoảng khi gặp khoảng trống sẽ không bao giờ ghi khoảng cuối cùng, vì vậy [0, 1, 2, 5, 6, 9] sẽ mất "9". Hãy kết thúc khoảng ở chỉ số cuối cùng nữa.
Ghi "a->a" cho một giá trị đơn lẻ. Một khoảng chỉ có một giá trị được viết là "a".
In các giá trị lớn dưới dạng ký hiệu khoa học. R chuyển một số thực double như 1000000000 thành 1e+09; hãy chuyển các giá trị thành số nguyên trước khi dán chúng.

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

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

O(n). Mỗi giá trị được duyệt một lần và mỗi khoảng được ghi một lần. Ngoài danh sách đầu ra, không gian phụ là O(1): điểm bắt đầu của khoảng hiện tại và một hoặc hai chỉ số.

Bạn xử lý một khoảng chỉ có một số như thế nào?

Kiểm tra xem phạm vi (range) bắt đầu và kết thúc ở cùng một giá trị (value) hay không. Nếu có, chỉ viết giá trị đó, như "9". Nếu không, viết giá trị bắt đầu, mũi tên rồi đến giá trị kết thúc, như "5->6". Với hai con trỏ (pointer), phép kiểm tra là i == j.

Summary Ranges có cần đầu vào được sắp xếp không?

Đúng. Phương thức chỉ so sánh các phần tử liền kề, nên dựa vào việc các số nguyên liên tiếp nằm cạnh nhau. Với đầu vào chưa được sắp xếp, hãy sắp xếp trước, việc này khiến bài toán có độ phức tạp O(n log n), hoặc đưa các giá trị vào một tập hợp băm rồi mở rộng từng dãy từ giá trị nhỏ nhất, như trong bài toán tìm dãy số liên tiếp dài nhất.

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

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [0, 1, 2, 5, 6, 9]

Đầu ra mong đợi

["0->2", "5->6", "9"]