So sánh hai mảng chưa sắp xếp JavaScript

chìa khóa rút ra. Một vấn đề tuyệt vời để tìm hiểu tối ưu hóa độ phức tạp thời gian bằng các phương pháp khác nhau. Các giải pháp hai con trỏ và bảng băm rất trực quan và đáng để khám phá

Hãy hiểu vấn đề

Cho hai mảng chưa sắp xếp X[] và Y[] có kích thước m và n, hãy viết chương trình tìm giao của hai mảng này

• Giả sử m > n và các phần tử trong cả hai mảng là khác nhau
• Giao điểm là danh sách các phần tử phổ biến có trong cả hai mảng
• Các phần tử trong đầu ra có thể theo bất kỳ thứ tự nào

ví dụ 1

Đầu vào. X[] = [3, 4, 6, 2, 8, 5, 9], Y[] = [6, 3, 2, 7, 5, 1]

đầu ra. [3, 6, 2, 5]

Giải trình. Các phần tử phổ biến là 3, 6, 2 và 5. Vậy giao điểm của cả hai mảng là 3, 6, 2 và 5

ví dụ 2

Đầu vào. X[] = [3, 4, 6, 7, 10, 12, 5], Y[] = [7, 11, 18, 15, 12]

đầu ra. [7, 12]

Giải trình. Các phần tử phổ biến là 7 và 12. Vì vậy, giao điểm của cả hai mảng là 7 và 12

ví dụ 3

Đầu vào. X[] = [3, 4, 6, 10, 5], Y[] = [7, 11, 18, 15, 12]

đầu ra. Không có yếu tố chung. Vì vậy, đầu ra là một mảng trống

Thảo luận phương pháp giải quyết

• Cách tiếp cận vũ phu  sử dụng các vòng lặp lồng nhau
• Sử dụng sắp xếp và tìm kiếm nhị phân
• Sử dụng sắp xếp và hai con trỏ
• Cách tiếp cận hiệu quả  sử dụng bảng băm

Cách tiếp cận vũ phu  sử dụng các vòng lặp lồng nhau

ý tưởng giải pháp

Ý tưởng cơ bản là chọn từng phần tử từ X[] và tìm kiếm tuyến tính trong Y[]. Chúng tôi thêm một phần tử vào danh sách đầu ra nếu nó có trong cả X[] và Y[]

• Chúng tôi chạy hai vòng lặp lồng nhau. Một vòng lặp bên ngoài từ i = 0 đến m - 1 để chọn từng phần tử X[i] và một vòng lặp bên trong từ j = 0 đến n - 1 để tìm kiếm tuyến tính X[i] trong Y[]
• Bất cứ khi nào chúng tôi tìm thấy một phần tử chung cho cả X[] và Y[] tôi. e. X[i] == Y[j], chúng tôi thêm bất kỳ một trong số đó vào giao lộ danh sách đầu ra
• Khi kết thúc các vòng lặp lồng nhau, chúng tôi trả về danh sách đầu ra giao lộ []

Mã giải pháp C++

vector findIntersection(int X[], int Y[], int m, int n)
{
    vector intersection;
    for (int i = 0; i < m; i = i + 1)
    {
        for (int j = 0; j < n; j = j + 1)
        {
            if (X[i] == Y[j])
            {
                intersection.push_back(X[i]);
                break;
            }
        }
    }
    return intersection;
}

Mã giải pháp Java

List findIntersection(int[] X, int[] Y, int m, int n) 
{
    List intersection = new ArrayList<>();
    for (int i = 0; i < m; i = i + 1) 
    {
        for (int j = 0; j < n; j = j + 1) 
        {
            if (X[i] == Y[j]) 
            {
                intersection.add(X[i]);
                break;
            }
        }
    }
    return intersection;
}

Mã giải pháp Python

def findIntersection(X, Y, m, n):
    intersection = []
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                intersection.append(X[i])
                break
    return intersection

phân tích giải pháp

Chúng tôi đang chạy hai vòng lặp lồng nhau và thực hiện các thao tác O(1) ở mỗi lần lặp. Trong trường hợp xấu nhất, vòng lặp bên trong sẽ chạy n lần. Vậy độ phức tạp thời gian = O(m) * O(*n) * O(1) = O(mn). Chúng tôi đang sử dụng không gian bổ sung không đổi, vì vậy độ phức tạp của không gian = O(1). Tại sao chúng ta không coi giao điểm của danh sách đầu ra là một phần của độ phức tạp của không gian?

Sử dụng tính năng sắp xếp và tìm kiếm nhị phân

ý tưởng giải pháp

Câu hỏi quan trọng là. Làm thế nào chúng ta có thể cải thiện độ phức tạp thời gian của phương pháp trên? . Chúng ta có thể suy nghĩ để cải thiện hiệu quả tìm kiếm phần tử X[i] trong Y[] không? . Nếu chúng ta sắp xếp mảng Y[], chúng ta có thể tìm kiếm từng phần tử X[i] bằng tìm kiếm nhị phân. Điều này có thể giúp cải thiện độ phức tạp về thời gian vì tìm kiếm nhị phân mất thời gian O(logn)

các bước giải quyết

• Chúng tôi khai báo một giao điểm danh sách đầu ra để lưu trữ các phần tử phổ biến
• Bây giờ chúng ta sắp xếp mảng Y[] theo thứ tự tăng dần. Chúng ta có thể sử dụng các thuật toán sắp xếp O(nlogn) như heap sort hoặc quick sort hoặc merge sort
• Chúng tôi chạy một vòng lặp từ i = 0 đến m - 1 và tìm kiếm từng phần tử X[i] trong mảng đã sắp xếp Y[] bằng tìm kiếm nhị phân. Bất cứ khi nào chúng tôi tìm thấy một phần tử chung cho cả X[] và Y[] tôi. e. X[i] == Y[j], chúng ta thêm nó vào danh sách đầu ra giao lộ[]
• Đến cuối vòng lặp, chúng tôi trả về danh sách đầu ra giao lộ []

Mã giải pháp C++

Mã giải pháp Java

Mã giải pháp Python

phân tích giải pháp

Chúng tôi đang sử dụng sắp xếp heap và tìm kiếm nhị phân lặp để triển khai. Độ phức tạp thời gian = Độ phức tạp thời gian chèn n phần tử của Y[] vào bảng băm + Độ phức tạp thời gian tìm kiếm m phần tử của X[] trong bảng băm = n * O(1) + m * O(1)) = O(m + . Độ phức tạp của không gian = O(n), để lưu trữ các giá trị trong bảng băm.  

Trong bài này chúng ta sẽ viết chương trình gộp 2 mảng chưa sắp xếp. Đầu ra là mảng được sắp xếp theo thứ tự tăng dần

Đầu vào. a[] = {10, 5, 15}

b[] = {20, 3, 2}

đầu ra. Mảng được hợp nhất theo thứ tự được sắp xếp {2, 3, 5, 10, 15, 20}

Đầu vào. a[] = {1, 10, 5, 15}

b[] = {20, 0, 2}

đầu ra. Mảng được hợp nhất theo thứ tự được sắp xếp {0, 1, 2, 5, 10, 15, 20}

Cách tiếp cận 1

Cách tiếp cận đầu tiên có thể được sử dụng ở đây là nối cả hai mảng và sắp xếp mảng đã nối. Chúng tôi tạo một mảng thứ ba có kích thước bằng hai mảng đầu tiên và sau đó chuyển tất cả các phần tử của cả hai mảng vào mảng kết quả. Sau thao tác nối thêm, chúng tôi sắp xếp mảng kết quả

mã C

đầu ra

The sorted array is:  1 2 3 5 7 10 12 15 20 22 100

Độ phức tạp về thời gian

O((n+m)log(n+m), trong đó n và m là kích thước của mảng

Độ phức tạp của không gian

O(n+m)

Cách tiếp cận 2

Cách tiếp cận trên có thể được tối ưu hóa khi chúng ta sử dụng ý tưởng sắp xếp đầu tiên sau đó hợp nhất nó với mảng thứ ba. Sắp xếp riêng cả hai mảng và hợp nhất chúng vào mảng kết quả

Làm cách nào để so sánh hai mảng không có thứ tự trong JavaScript?

Làm cách nào để so sánh các phần tử của 2 mảng trong JavaScript?

Bạn có thể sử dụng == để so sánh các mảng không?

Làm cách nào để so sánh sâu hai mảng trong JavaScript?