Check if an Array Is Sorted

Q: Mảng có các phần tử bằng nhau có được sắp xếp không?

Đúng, theo thứ tự không giảm: [4, 4, 4] đã được sắp xếp vì không phần tử nào lớn hơn phần tử tiếp theo. Nếu bài toán yêu cầu thứ tự tăng nghiêm ngặt, hãy thay đổi phép kiểm tra để loại cả các phần tử liền kề bằng nhau.

Q: Bạn có thể sắp xếp một bản sao rồi so sánh với bản gốc không?

Đúng là nó cho ra đáp án chính xác, nhưng tốn thời gian O(n log n) và bộ nhớ phụ O(n) . Việc kiểm tra các phần tử liền kề không cần tạo bản sao và có thể dừng ngay khi gặp bước giảm đầu tiên.

Người mớiMảng và chuỗi

+10

Bạn nhận được một mảng số nguyên nums. Trả về true nếu mảng được sắp xếp theo thứ tự không giảm, nghĩa là mỗi phần tử nhỏ hơn hoặc bằng phần tử đứng sau nó, và trả về false nếu không. Các phần tử liền kề bằng nhau vẫn được chấp nhận: [2, 2, 3] được xem là đã sắp xếp. Mảng có một phần tử được xem là đã sắp xếp.

Hàm

isSorted(nums: integer-array) → boolean

numsinteger-array: mảng số nguyên cần kiểm tra
Trả vềboolean: true khi mọi phần tử đều nhỏ hơn hoặc bằng phần tử tiếp theo, false nếu không

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Ví dụ

Đầu vào: nums = [1, 3, 3, 7]
Đầu ra: true
Giải thích: Mỗi bước đều tăng hoặc giữ nguyên: từ 1 đến 3, từ 3 đến 3, từ 3 đến 7. Giá trị 3 lặp lại là được phép, nên đáp án là true.

Câu hỏi mở rộng

Bạn sẽ kiểm tra một mảng có thể được sắp xếp theo chiều tăng dần hoặc giảm dần chỉ trong một lượt như thế nào?

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

Mảng được sắp xếp khi và chỉ khi không có phần tử nào lớn hơn phần tử đứng ngay sau nó. Vì vậy, chỉ cần kiểm tra một lượt qua n-1 cặp phần tử liền kề là đủ để xác định, và lượt kiểm tra có thể dừng ở lần đầu tiên gặp một bước giảm.

Sắp xếp một bản sao rồi so sánh

Ý tưởng

Mảng đã sắp xếp là mảng không thay đổi khi được sắp xếp: hãy sắp xếp một bản sao rồi so sánh với nums ở từng vị trí. Với [2, 5, 4, 9], bản sao [2, 4, 5, 9] khác ở vị trí 1, nên đáp án là false.

Việc sắp xếp có độ phức tạp O(n log n), cần khoảng 6 × 10^4 phép so sánh với 5000 số, cộng thêm O(n) bộ nhớ cho bản sao, và đọc toàn bộ mảng ngay cả khi cặp đầu tiên đã không đúng thứ tự.

Thuật toán

Sao chép nums để giữ nguyên bản gốc.
Sắp xếp bản sao theo thứ tự số tăng dần.
So sánh bản sao với nums ở từng vị trí.
Trả về true nếu mọi vị trí đều khớp, nếu không thì trả về false.

def isSorted(nums):
    # sorted returns a new list, so nums itself is left as it was.
    return sorted(nums) == nums

So sánh từng cặp phần tử liền kề

Ý tưởng

Vì các phép so sánh ≤ có tính bắc cầu (a ≤ b và b ≤ c suy ra a ≤ c), nên n-1 cặp phần tử liền kề bao quát mọi cặp vị trí, và mảng chưa được sắp xếp luôn có một cặp phần tử liền kề giảm dần. Vì vậy, duyệt i từ 1 đến n-1 và trả về false tại vị trí đầu tiên thỏa mãn nums[i-1] > nums[i]. Với [2, 5, 4, 9], đó là cặp (5, 4), còn 9 không bao giờ được đọc. Các phần tử liền kề bằng nhau vẫn đạt, vì chỉ có > là không đạt.

Mỗi cặp được so sánh một lần: độ phức tạp thời gian O(n) và bộ nhớ O(1).

Thuật toán

Lặp i từ 1 đến n-1.
Nếu nums[i-1] > nums[i], trả về false.
Nếu vòng lặp kết thúc, trả về true. Mảng có một phần tử sẽ bỏ qua vòng lặp và được xem là đã sắp xếp.

def isSorted(nums):
    for i in range(1, len(nums)):
        # One step down anywhere breaks the order.
        if nums[i - 1] > nums[i]:
            return False
    return True

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

Xem hai phần tử kề nhau bằng nhau là lỗi. Kiểm tra nums[i-1] >= nums[i] sẽ loại bỏ [1, 3, 3, 7].
Đọc vượt quá phần tử cuối. Vòng lặp chạy từ 0 đến n-1 mà so sánh nums[i] với nums[i+1] sẽ đọc bên ngoài mảng ở bước cuối. Bắt đầu từ i = 1 và so sánh với i-1.
Trừ thay vì so sánh. nums[i] - nums[i-1] >= 0 gây tràn số nguyên 32 bit với [-1000000000, 1000000000]: 2 × 10^9 bị cuộn thành số âm và mảng bị báo là chưa sắp xếp. Hàm so sánh qsort viết dưới dạng x - y cũng gặp lỗi tương tự.
Sắp xếp số dưới dạng văn bản. Trong JavaScript, sort() không có hàm so sánh sẽ xếp 10 trước 9, nên cách sắp xếp rồi so sánh sẽ cho kết quả sai.

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

Làm thế nào để kiểm tra xem một mảng đã được sắp xếp chưa?

So sánh từng phần tử với phần tử tiếp theo. Nếu có phần tử nào lớn hơn phần tử bên phải nó, mảng chưa được sắp xếp và bạn có thể dừng lại; nếu đi đến cuối mà không tìm thấy phần tử nào như vậy thì mảng đã được sắp xếp. Cách này mất thời gian O(n) và cần thêm O(1) bộ nhớ.

Mảng có các phần tử bằng nhau có được sắp xếp không?

Đúng, theo thứ tự không giảm: [4, 4, 4] đã được sắp xếp vì không phần tử nào lớn hơn phần tử tiếp theo. Nếu bài toán yêu cầu thứ tự tăng nghiêm ngặt, hãy thay đổi phép kiểm tra để loại cả các phần tử liền kề bằng nhau.

Bạn có thể sắp xếp một bản sao rồi so sánh với bản gốc không?

Đúng là nó cho ra đáp án chính xác, nhưng tốn thời gian O(n log n) và bộ nhớ phụ O(n). Việc kiểm tra các phần tử liền kề không cần tạo bản sao và có thể dừng ngay khi gặp bước giảm đầu tiên.

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

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [1, 3, 3, 7]

Đầu ra mong đợi

true