सॉर्टिंग परिणाम सरणी

Question

मुझे एडोब साक्षात्कार में इस प्रश्न से पूछा गया था:

हमारे पास एक पूर्णांक सरणी है जो आरोही क्रम में क्रमबद्ध है। हमारे पास 3 पूर्णांक A, B और C भी हैं। हमें सरणी में प्रत्येक तत्व x के लिए A*x*x + B*x + C लागू करने और संबंधित क्रमबद्ध सरणी को वापस करने की आवश्यकता है।

उदाहरण मैं दिया गया था:

Input array = -1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

प्रत्येक तत्व के लिए सूत्र लागू का परिणाम = -4 -1 0 -1 -4 -9
तो अपेक्षित परिणाम = -9 -4 -4 -1 -1 0 (क्रमबद्ध)

मेरे सबसे अच्छा समाधान सूत्र लागू करते हैं और यह सॉर्ट करने के लिए था परिणामस्वरूप O(nlogn) समाधान। मैं इसे बेहतर नहीं कर सका।

यह सुधार करने में किसी भी मार्गदर्शन उपयोगी है।

Answer 1

आप O(n) में ऐसा कर सकते हैं। बहुपद होता है जो जब

2 * A * x + B = 0 

ताकि

x_min = -B/2 * A. 

फिर, सरणी चलना जब तक आप x_min को पूर्णांक निकटतम लगता है की न्यूनतम मूल्य का पता लगाएं। यह O(n) है। यहां से |x_min - left||x_min - right| से छोटा या बड़ा है या नहीं, इस तत्व के बाएं या दाएं से लगातार चुनते हैं। परिणामी क्रम में इन बिंदुओं पर बहुपद का मूल्यांकन करने के मूल्यों को वापस करें। यह O(n) है।

मतलब यह है कि A सकारात्मक है। आप इसी तरह नकारात्मक A के मामले को संभाल सकते हैं।

उदाहरण:

input array = -1 0 1 2 3 4 A = -1, B = 2, C = -1 

यहाँ, अधिकतम मूल्य x_max = -2/2 * -1 = 1 पर होता है। इनपुट सरणी से, निकटतम मान 1, तीसरा तत्व है। फिर हम 1 की दूरी के आधार पर निम्न क्रम में तत्वों को क्रमशः चुनते हैं।

1, 0, 2, -1, 3, 4 

फिर, क्योंकि A नकारात्मक है, हम उलटे क्रम

4, 3, -1, 2, 0, 1 

में इन चलाने के लिए और उन पर

-9, -4, -4, -1, -1, 0 

हो गया बहुपद का मूल्यांकन करने के लिए है।

ध्यान दें कि हम परवलय का एक विशेष संपत्ति का शोषण कर रहे हैं। अर्थात्, x कम से कम x_extreme और A सकारात्मक के लिए, इस तरह के x को बहुपद लागू करने x की एक कम कार्य है। x से अधिक x_extreme और A सकारात्मक के लिए, ऐसे x को बहुपद लागू करने x की एक बढ़ती हुई कार्य है।(इसी प्रकार के तर्क लागू होता है अगर A नकारात्मक है।) इस प्रकार, दो टुकड़े, उन xx_extreme की तुलना में कम है और उन xx_extreme से अधिक में सरणी विभाजन। फिर क्रमबद्ध दो सरणी के साथ समाप्त करने के लिए इन दो टुकड़ों में बहुपद लागू करें। अब इन सॉर्ट किए गए सरणी में क्रमबद्ध विलय लागू करें। ध्यान दें कि उपर्युक्त वर्णन प्रभावी रूप से विलय प्रकार है।

Answer 2

समीकरण को देखते हुए parabolic है। तो इसे सॉर्ट किए गए सरणी में लगाने का नतीजा एक सरणी में होगा जिसके उप-सरणी के साथ अधिकतम/न्यूनतम अधिकतम बाएं और दाएं क्रमबद्ध होंगे।

आपके मामले में अधिकतम 0 है और बायीं [-4 -1] को उप सरणी अपने अधिकार [-1 -4 -9] को आरोही क्रम और उप सरणी में क्रमबद्ध हो जाता घटते क्रम में क्रमबद्ध किया गया है।

तुम सब करने की ज़रूरत है मर्ज इन अनुसार क्रमबद्ध सरणियों जो समय में रेखीय है।

तो एल्गोरिथ्म है:

1. प्रत्येक तत्व
2. ढूँढें अधिकतम पर समीकरण लागू करें/न्यूनतम
3. subarrays मर्ज

Answer 3

आप पहचान सकते हैं कि करने के लिए द्विघात लागू करने के परिणाम डेटा को लगभग क्रमबद्ध किया गया है (जैसा कि ऊपर दिए गए उत्तरों में वर्णित है, या यह मानकर कि डिग्री एन के बहुपद का व्युत्पन्न निरंतर है, डिग्री एन -1 का है, और इसमें अधिकांश एन शून्य हैं)।

तो अगर आपको लगता है कि कुछ लगभग हल कर डेटा (जैसे एक mergesort जो इसे ध्यान में रखता है के रूप में) के साथ चालाक करता है अपने पुस्तकालय में एक छँटाई दिनचर्या है, तो आप सिर्फ डेटा इसे फेंक और रैखिक प्रदर्शन की उम्मीद कर सकते हैं। वेब सर्च कर रहे हैं Which sort algorithm works best on mostly sorted data? जो http://svn.python.org/projects/python/trunk/Objects/listsort.txt पर अंक पाता है।

Answer 4

समाधान O(N) है और किसी भी पथरी प्रदर्शन करने के लिए कोई जरूरत नहीं है, हालांकि यह वक्र के आकार को समझने के लिए मदद करता है।

जवाब ऊपर सबसे सहज बात कर और समीकरण को हल न्यूनतम या अधिकतम खोजने के लिए और फिर सूची विभाजित कर रहे हैं।

पहले व्युत्पन्न की गणना करने में एक फायदा है लेकिन वास्तव में ऐसा करने की आवश्यकता नहीं है, और न ही हमें इस समय अधिकतम या न्यूनतम बिंदु खोजने की आवश्यकता है।

बस पता है कि यह एक ही दिशा में तो दूसरी दिशा में वापस ले जाने के कर सकते हैं और लेकिन दिशा एक बार से अधिक कभी नहीं बदलेगा।

हम प्रत्येक तरफ से शुरू होने जा रहे हैं और दोनों तरफ से फिर से भरने जा रहे हैं जब तक कि हम बीच में कहीं भी विलय न करें। कुछ और करने से पहले हमें प्रत्येक छोर पर दिशा की जांच करने की ज़रूरत है, जिसे हम केवल दो तत्वों की तुलना करके करेंगे। तो हम देखते हैं कि एक अंत ऊपर की तरफ बढ़ रहा है और दूसरा नीचे है।

अगर हम N तत्व का कहना है कि हम डेटा X[0] और X[N-1] तो f(X[0]) और f(X[N-1]) और f(X[1]) और f(X[N-2]) गणना डालते हैं। यदि f(X[0]) < f(X[1]) और f(X[N-1]) > f(X[N-2]) तो वास्तव में हमारा सभी डेटा अधिकतम/न्यूनतम का एक पक्ष है और इस प्रकार पहले से ही क्रमबद्ध है। वही अगर तुलना दूसरी दिशा में हैं।(एक दिशा को रिवर्स की आवश्यकता हो सकती है)।

अन्यथा सिर्फ दोनों सिरों से मर्ज है, इस प्रकार f(X[0]) और f(X[N-1]) या तो मॅक्सिमा या उनके उप पर्वतमाला की न्यूनतम (जैसा कि हम पहले की तुलना से जानते हैं) कर रहे हैं और मर्ज किए गए सूची जो भी से उचित दिशा है बनाएँ।

अपने डेटा के लिए आवेदन:

-1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

f = [ -4, -1, 0, -1, -4, -9 ] 

-4 < -1 और -9 < -4 तो हम बिंदु को पार करते हैं और हम प्रत्येक के अंत में न्यूनतम है।

-9 is lower than -4 
-4 and -4 are equal so push both 
-1 and -1 are equal so push both 
0 remains. 

our sequence is [-9, -4, -4, -1, -1, 0 ]