So sánh hai mảng trong Javascript - Trở khác biệt

Question

Giả sử chúng ta có:

array1 = ['A', 'B', 'C', 'D', 'E']; array2 = ['C', 'E']; 

Có một chứng minh và giải pháp nhanh chóng để so sánh hai mảng với nhau, trở về một mảng mà không có giá trị xuất hiện trong cả hai mảng (C và E ở đây). Vì vậy:

array3 = ['A', 'B', 'D'] 

phải là đầu ra của giải pháp. (jquery có thể được tham gia)

thx.

Answer 1

Đây là sự khác biệt được đặt. Triển khai đơn giản là:

jQuery.grep(array1, function(el) 
        { 
         return jQuery.inArray(el, array2) == -1; 
        }); 

Đây là O (m * n), nơi đó là kích thước của mảng. Bạn có thể làm điều đó trong O (m + n), nhưng bạn cần phải sử dụng một số loại bộ băm. Bạn có thể sử dụng một đối tượng JavaScript như một bộ băm đơn giản cho các chuỗi. Đối với các mảng tương đối nhỏ, điều trên phải ổn.

Answer 2

giải pháp nhanh đã được chứng minh mà tôi biết là tìm kiếm nhị phân mà bạn có thể sử dụng sau khi bạn sắp xếp một trong các mảng. vì vậy giải pháp cần có thời gian phụ thuộc vào thuật toán sắp xếp. nhưng ít nhất là log (N).

Answer 3

Tôi chấp nhận Giải pháp Matthews, nhưng không muốn bỏ qua một giải pháp nhanh hơn khác mà tôi vừa tìm thấy.

var list1 = [1, 2, 3, 4, 5, 6]; 
var list2 = ['a', 'b', 'c', 3, 'd', 'e']; 
var lookup = {}; 

for (var j in list2) { 
     lookup[list2[j]] = list2[j]; 
    } 

    for (var i in list1) { 
     if (typeof lookup[list1[i]] != 'undefined') { 
      alert('found ' + list1[i] + ' in both lists'); 
      break; 
} 
} 

Nguồn: Optimize Loops to Compare Two Arrays