Hoán đổi các phần tử của hai chuỗi, sao cho sự khác biệt của các phần tử tổng được tối thiểu.

Question

Một câu hỏi phỏng vấn:

Cho hai chuỗi số nguyên không ra lệnh a và b, kích thước của chúng là n, tất cả số được lựa chọn một cách ngẫu nhiên: Trao đổi các yếu tố của a và b, sao cho tổng của các yếu tố của a trừ đi tổng các phần tử của b là tối thiểu.

Với ví dụ:

a = [ 5 1 3 ] 
b = [ 2 4 9 ] 

Kết quả là (1 + 2 + 3) - (4 + 5 + 9) = -12.

Thuật toán của tôi: Sắp xếp chúng lại với nhau và sau đó đặt nhỏ nhất đầu tiên n ints trong a và để lại trong b. Nó là O (n lg n) trong thời gian và O (n) trong không gian. Tôi không biết làm thế nào để cải thiện nó thành một thuật toán với O (n) trong thời gian và O (1) trong không gian. O (1) có nghĩa là chúng ta không cần thêm không gian ngoại trừ seq 1 và 2.

Bất kỳ ý tưởng nào?

Một câu hỏi khác là: Nếu chúng ta cần giảm thiểu giá trị tuyệt đối của sự khác biệt (giảm thiểu |sum(a) - sum(b)|) thì sao?

Tư duy python hoặc C++ được ưu tiên.

Answer 1

giải pháp sửa đổi:

1. Merge cả hai danh sách x = merge (a, b).

2. Tính trung bình của x (độ phức tạp O (n) Xem http://en.wikipedia.org/wiki/Selection_algorithm)

3. Sử dụng này yếu tố hoán đổi trung bình giữa a và b. Đó là, tìm một phần tử trong một đó là ít hơn trung bình, tìm thấy một trong b đó là hơn trung bình và trao đổi chúng

cuối cùng phức tạp: O (n)

Giảm thiểu sự khác biệt tuyệt đối là NP hoàn chỉnh vì nó tương đương với vấn đề ba lô.

Answer 2

gì đi vào tâm trí của tôi là sau phác thảo thuật toán:

1. C = A v B
2. Partitially loại #A (số A) Các yếu tố của C
3. Trừ tổng các cuối cùng # B Elements từ C từ tổng cáC#A Elements đầu tiên từ C.

bạn nên để ý, mà bạn không cần phải sắp xếp tất cả các yếu tố, nó là đủ để tìm thứ e số của Một yếu tố nhỏ nhất.Ví dụ bạn đưa ra:

1. C = {5, 1, 3, 2, 4, 9}
2. C = {1, 2, 3, 5, 4, 9}
3. (1 + 2 + 3) - (5 + 4 + 9) = -12

một C++ giải pháp:

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main() 
{ 
    // Initialize 'a' and 'b' 
    int ai[] = { 5, 1, 3 }; 
    int bi[] = { 2, 4, 9 }; 
    std::vector<int> a(ai, ai + 3); 
    std::vector<int> b(bi, bi + 3); 

    // 'c' = 'a' merged with 'b' 
    std::vector<int> c; 
    c.insert(c.end(), a.begin(), a.end()); 
    c.insert(c.end(), b.begin(), b.end()); 

    // partitially sort #a elements of 'c' 
    std::partial_sort(c.begin(), c.begin() + a.size(), c.end()); 

    // build the difference 
    int result = 0; 
    for (auto cit = c.begin(); cit != c.end(); ++cit) 
     result += (cit < c.begin() + a.size()) ? (*cit) : -(*cit); 

    // print result (and it's -12) 
    std::cout << result << std::endl; 
}