दो अनुक्रमों के तत्वों को स्वैप करें, जैसे कि तत्व-रकम का अंतर न्यूनतम हो जाता है।

Question

एक साक्षात्कार प्रश्न:

को देखते हुए दो गैर-आदेश दिया पूर्णांक दृश्यों a और b, उनके आकार n, सभी संख्या बेतरतीब ढंग से चुना जाता है है: a और b के तत्वों, ऐसे तत्वों का योग है जो Exchange a की संख्या b के तत्वों की राशि न्यूनतम है।

उदाहरण को देखते हुए:

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

परिणाम (1 + 2 + 3) है - (4 + 5 + 9) = -12।

मेरा एल्गोरिदम: उन्हें एक साथ क्रमबद्ध करें और फिर a में पहले सबसे छोटे n इनट्स डालें और b में छोड़ दें। यह समय में ओ (एन एलजी एन) और अंतरिक्ष में ओ (एन) है। मुझे नहीं पता कि समय में ओ (एन) के साथ एल्गोरिदम में इसे कैसे सुधारें और ओ (1) अंतरिक्ष में कैसे करें। ओ (1) का मतलब है कि हमें सीईसी 1 और 2 को छोड़कर अधिक अतिरिक्त जगह की आवश्यकता नहीं है।

कोई विचार?

एक वैकल्पिक प्रश्न होगा: क्या होगा यदि हमें मतभेदों के पूर्ण मूल्य को कम करने की आवश्यकता है (|sum(a) - sum(b)| को कम करें)?

एक अजगर या सी ++ सोच को प्राथमिकता दी जाती है।

Answer 1

संशोधित समाधान:

1. मर्ज दोनों सूचियों एक्स = मर्ज (क, ख)।

2. एक्स की औसत की गणना (जटिलता हे (एन) http://en.wikipedia.org/wiki/Selection_algorithm देखें)

3. ए और बी के बीच इस मंझला स्वैप तत्वों का उपयोग करना। यही कारण है, यह है कि औसत से कम है एक में एक तत्व को खोजने ख है कि अधिक से अधिक मंझला है में एक खोजने के लिए और उन्हें स्वैप

अंतिम जटिलता: हे (एन)

को न्यूनतम निरपेक्ष अंतर एनपी पूरा हो गया है चूंकि यह knapsack समस्या के बराबर है।

Answer 2

क्या मेरे मन में आता है पीछा कर रहा है एल्गोरिथ्म रूपरेखा:

1. सी = एक वी बी सी
2. की
3. Partitially तरह #A (ए की संख्या) तत्वों पिछले # का योग घटाएँ सी
से पहले #A तत्वों का योग से सी से बी तत्वों

आप नोटिस देना चाहिए कि आप सभी तत्वों सॉर्ट करने के लिए की जरूरत नहीं है , यह वें खोजने के लिए पर्याप्त है ई सबसे छोटे तत्वों की संख्या।आपका उदाहरण दिया:

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

एक C++ समाधान:

#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; 
}