Làm thế nào để tính toán sự khác biệt giữa hai bộ trong C?

Question

Tôi có hai mảng, nói A và B với | A | = 8 và | B | = 4. Tôi muốn tính toán sự khác biệt thiết lập A-B. Làm cách nào để tiếp tục? Xin lưu ý rằng không có yếu tố lặp lại trong một trong các bộ.

Chỉnh sửa: Cảm ơn mọi người vì vô số các giải pháp thanh lịch. Kể từ khi tôi đang trong giai đoạn tạo mẫu của dự án của tôi, bây giờ tôi thực hiện các giải pháp đơn giản nhất được nói bởi Brian và Owen. Nhưng tôi đánh giá cao việc sử dụng thông minh các cấu trúc dữ liệu như được đề xuất ở đây bởi phần còn lại của bạn, mặc dù tôi không phải là nhà khoa học máy tính mà là kỹ sư và không bao giờ nghiên cứu cấu trúc dữ liệu như một khóa học. Có vẻ như đó là khoảng thời gian tôi thực sự nên bắt đầu đọc CLRS mà tôi đã trì hoãn trong một thời gian :) Cảm ơn một lần nữa!

Answer 1

lặp qua mỗi phần tử của A, nếu mỗi người trong số những yếu tố đang không ở trong B, sau đó thêm chúng vào một bộ mới C.

Answer 2

Nó phụ thuộc vào cách bạn muốn để đại diện cho bộ của bạn, nhưng nếu họ chỉ là các bit được đóng gói sau đó bạn có thể sử dụng các toán tử bitwise, ví dụ D = A & ~B; sẽ cung cấp cho bạn sự khác biệt thiết lập A-B nếu các bộ phù hợp với một loại số nguyên. Đối với các tập hợp lớn hơn, bạn có thể sử dụng các loại số nguyên và lặp lại, ví dụ:

for (i = 0; i < N; ++i) 
{ 
    D[i] = A[i] & ~B[i]; 
} 

Answer 3

mảng loại A và B
kết quả sẽ nằm trong C
cho một - các elem đầu tiên của A
let b - các elem đầu tiên của B
thì:
1) trong khi một < b: chèn vào C và a = elem tiếp theo của A
2) trong khi a> b: b = elem tiếp theo của B
3) nếu a = b: a = elem tiếp theo của A và b = elem tiếp theo của B
4) nếu b kết thúc: chèn r est của A thành C và dừng
5) nếu đi đến kết thúc: ngừng

Answer 4

Đối với bộ lớn hơn tôi muốn đề nghị sắp xếp những con số và lặp qua chúng bằng cách bắt chước mã tại http://www.cplusplus.com/reference/algorithm/set_difference/ đó sẽ là O (N * logN), nhưng kể từ khi kích thước thiết lập là quá nhỏ, các giải pháp được đưa ra bởi Brian có vẻ tốt mặc dù nó về mặt lý thuyết chậm hơn tại O (N^2).

Answer 5

Sau đây giả định các bộ được lưu trữ dưới dạng vùng chứa được sắp xếp (như std :: set does).

Có một thuật toán phổ biến để hợp nhất hai danh sách được sắp xếp để tạo ra một danh sách thứ ba. Ý tưởng là khi bạn nhìn vào đầu của hai danh sách, bạn có thể xác định đó là thấp hơn, trích xuất đó, và thêm nó vào đuôi của đầu ra, sau đó lặp lại.

Có các biến thể phát hiện trường hợp hai đầu bằng nhau và xử lý đặc biệt này. Đặt giao lộ và công đoàn là những ví dụ về điều này.

Với sự khác biệt không đối xứng được đặt, điểm mấu chốt là đối với A-B, khi bạn giải nén đầu B, bạn loại bỏ nó. Khi bạn trích xuất phần đầu của A, bạn thêm nó vào đầu vào trừ khi phần đầu của B bằng nhau, trong trường hợp này bạn cũng lấy ra phần đầu và loại bỏ cả hai.

Mặc dù phương pháp này được thiết kế cho cấu trúc dữ liệu truy cập tuần tự (và lưu trữ băng vv), đôi khi rất hữu ích khi thực hiện điều tương tự cho cấu trúc dữ liệu truy cập ngẫu nhiên miễn là nó có hiệu quả. Và bạn không nhất thiết phải trích xuất mọi thứ cho thực - bạn có thể sao chép và thay vào đó.

Điểm mấu chốt là bạn bước qua các đầu vào tuần tự, luôn nhìn vào giá trị còn lại thấp nhất tiếp theo, để (nếu đầu vào không có bản sao), bạn sẽ thấy các mục phù hợp. Do đó, bạn luôn biết liệu giá trị thấp nhất tiếp theo của bạn để xử lý là một mục từ A không khớp với B và mục trong B không có kết quả phù hợp trong A hoặc một mục bằng nhau trong cả A và B.

Nói chung, thuật toán cho sự khác biệt thiết lập phụ thuộc vào sự biểu diễn của tập hợp. Ví dụ, nếu tập hợp được biểu diễn dưới dạng bit-bit, thì ở trên sẽ quá phức tạp và chậm - bạn chỉ cần lặp qua các vectơ thực hiện các thao tác bitwise. Nếu tập hợp được biểu diễn như là một hashtable (như trong tr1 unordered_set) ở trên là sai vì nó đòi hỏi đầu vào được đặt hàng.

Nếu bạn có mã cây nhị phân mà bạn đang sử dụng cho bộ, một tùy chọn tốt là chuyển đổi cả hai cây thành danh sách được liên kết, làm việc trên danh sách, sau đó chuyển danh sách kết quả thành cây cân bằng hoàn hảo. Sự khác biệt thiết lập danh sách liên kết rất đơn giản và hai chuyển đổi có thể sử dụng lại cho các hoạt động tương tự khác.

EDIT

Trên phức tạp - sử dụng các thuật toán hợp nhất giống như ra lệnh là O (n) cung cấp bạn có thể làm traversals trong trật tự trong thời gian O (n). Chuyển đổi thành một danh sách và ngược lại cũng là O (n) vì mỗi trong ba bước là O (n) - cây-to-list, set-sự khác biệt và danh sách-to-tree.

Danh sách cây được đưa vào danh sách về cơ bản thực hiện quá trình truyền tải độ sâu đầu tiên, phá hủy cây khi di chuyển. Có một thủ thuật để làm cho lặp đi lặp lại này, lưu trữ "ngăn xếp" trong các nút được xử lý một phần - thay đổi một con trỏ con trỏ trái thành con trỏ cha mẹ ngay trước khi bạn bước tới con trái. Đây là một ý tưởng tốt nếu cây có thể lớn và không cân bằng.

Chuyển đổi danh sách thành cây về cơ bản liên quan đến độ sâu đầu tiên của cây tưởng tượng (dựa trên kích thước, được biết từ đầu) xây dựng nó cho thực như bạn đi. Ví dụ: nếu cây có 5 nút, bạn có thể nói rằng thư mục gốc sẽ là nút 3. Bạn recurse xây dựng một cây con trái hai nút, sau đó lấy mục tiếp theo từ danh sách cho thư mục gốc đó, sau đó recurse để xây dựng một hai -nút bên phải.

Chuyển đổi danh sách thành cây không cần phải được triển khai lặp lại - đệ quy là tốt vì kết quả luôn được cân bằng hoàn hảo. Nếu bạn không thể xử lý độ sâu đệ quy log, bạn hầu như không thể xử lý toàn bộ cây đó.

Answer 6

Triển khai đối tượng đã đặt trong C. Bạn có thể thực hiện việc này bằng bảng băm cho bộ nhớ cơ bản. Đây rõ ràng là một bài tập không tầm thường, nhưng một vài giải pháp OpenSource tồn tại. Sau đó, bạn chỉ cần thêm tất cả các phần tử của A và sau đó lặp lại trên B và loại bỏ bất kỳ phần tử nào trong tập hợp của bạn.

Điểm mấu chốt là sử dụng cấu trúc dữ liệu phù hợp cho công việc.