दो एरे दिए गए इंडेक्स को देखते हैं जो योग ए [i] * | बी [i] -B [k] को कम करता है।

Question

मुझे दो एरे दिए गए हैं जिनमें प्राकृतिक संख्याएं, ए और बी शामिल हैं, और मुझे इंडेक्स को खोजने की आवश्यकता है जो राशि ए [i] * | बी [i] -B [k] को कम करता है। i = 0 से n-1 तक। (दोनों सरणीओं की लंबाई समान है) ओ (एन^2) में यह करना आसान है, मैं सिर्फ 0 और एन -1 के बीच सभी के लिए सभी रकम की गणना करता हूं, लेकिन मुझे बेहतर रन टाइम जटिलता की आवश्यकता है।

कोई विचार? धन्यवाद!

Answer 1

आप बी में मानों के आधार पर पहले और दोनों स्कैन करने के बाद ओ (nlogn) समय में ऐसा कर सकते हैं।

एक बार सरणी क्रमबद्ध हो जाने के बाद, बी [i]> = बी [के] अगर मैं> के और बी [i] < = बी [के] यदि मैं < = के, तो राशि को फिर से लिखा जा सकता है:

sum A[i] * abs(B[i]-B[k]) = sum A[i]*(B[i]-B[k]) for i=k..n-1 
          + sum A[i]*(B[k]-B[i]) for i=0..k-1 

    = sum A[i]*B[i] for i=k..n-1 
     - B[k] * sum A[i] for i=k..n-1 
     + B[k] * sum A[i] for i = 0..k-1 
     - sum A[i]*B[i] for i = 0..k-1 

आप समय हे (एन) में रकम के सभी precalculate कर सकते हैं जो तब आप में हे (एन) हर स्थिति में लक्ष्य राशि का मूल्यांकन कर सकते हैं और जो सबसे अच्छा स्कोर देता है कश्मीर के लिए मूल्य का चयन करें।

Answer 2

मुझे विश्वास है कि मैं यह कर सकता हूं ओ (एन लॉग एन) है।

सबसे पहले, B सरणी को सॉर्ट करें, A सरणी (और क्रमपरिवर्तन को याद रखना) पर समान क्रमपरिवर्तन लागू करें। यह ओ (एन लॉग एन) भाग है। चूंकि हम सभी के बराबर हैं, इसलिए ए और बी सरणी में समान क्रमपरिवर्तन लागू करना न्यूनतम नहीं बदलता है।

एक क्रमबद्ध B सरणी के साथ, बाकी एल्गोरिदम वास्तव में ओ (एन) है।

प्रत्येक के लिए, एक सरणी सी _के [i] = | बी [i] - बी [के] |

(नोट:। हम वास्तव में सी _{कश्मीर} का निर्माण नहीं होगा ... हम सिर्फ आसान तर्क के लिए एक अवधारणा के रूप में उपयोग करेंगे)

गौर करें कि मात्रा हम (के अधिक) कम करने के लिए कोशिश कर रहे हैं ए [i] * सी _के [i] की राशि। के आगे जाना है और कि एक नाम दे दो:

परिभाषित करें: एस _{कश्मीर} = Σ एक [i] * सी _{कश्मीर} [i]

अब, किसी विशेष कश्मीर के लिए, क्या सी करता _{कश्मीर} हमशक्ल?

ठीक है, सी _के [के] = 0, जाहिर है।

ज्यादा दिलचस्प है, क्योंकि बी सरणी सॉर्ट हो जाता है, हम निरपेक्ष मूल्य के संकेत से छुटकारा पाने के कर सकते हैं:

• सी _{कश्मीर} [i] = बी [k] - बी [i], 0 के लिए < = मैं < कश्मीर
• सी _{कश्मीर} [i] = 0, के लिए मैं = k
• सी _{कश्मीर} [i] = बी [i] - बी [k], कश्मीर < के लिए मैं < n

चलिए दो और चीजों को परिभाषित करते हैं।

परिभाषा: टी _{कश्मीर} = Σ एक [i] के लिए 0 < = मैं < कश्मीर

परिभाषा: यू _{कश्मीर} = Σ एक [i] कश्मीर < के लिए मैं < n

(यही है, टी _के ए यू _के के पहले के -1 तत्वों का योग है ए के पहले के तत्वों के अलावा सभी का योग है।

कुंजी अवलोकन: एस _{कश्मीर} को देखते हुए, टी _{कश्मीर}, और यू _{कश्मीर}, हम एस निरंतर में _{k + 1}, टी _{k + 1}, और यू _{k + 1} गणना कर सकता है पहर। कैसे?

टी और यू आसान हैं।

सवाल है, हम कैसे एस _{k + 1} को एस _{कश्मीर} से मिलता है?

पर विचार करें क्या सी _{कश्मीर} को होता है जब हम सी _{k + 1} में जाते हैं। हम बस बी से [के + 1] -बी [के] को 0 से के के प्रत्येक तत्व में जोड़ते हैं, और हम सी के 1 से एन तक (सी साबित) से प्रत्येक तत्व से उसी राशि को घटाते हैं। इसका मतलब है कि हमें टी _के * (बी [के + 1] - बी [के]) जोड़ने और यू _के * (बी [के + 1] - बी [के]) को एस _{से प्राप्त करने की आवश्यकता है के} एस _{के + 1} पर।

बीजगणितीय ... एस _{के पहले के नियम} ए [i] * (बी [के] - बी [i]) के 0 से के -1 के योग के बराबर हैं। (- बी [i] बी [k + 1])

के बीच का अंतर

एस _{कश्मीर के पहले कश्मीर मामले + 1} 0 से योग K-1 का एक [i] * करने के लिए कर रहे हैं ये योग है, 0 से के -1 तक, (ए [i] * (बी [के + 1] - बी [i]) - (ए [i] * (बी [के] - बी [i]))। ए [i] शब्दों को फैक्टर करें और बी [i] शर्तों को 0 [के] 1 से प्राप्त करने के लिए शर्तों को रद्द करें [i] * (बी [के + 1] - बी [के]), जो कि है बस टी _के * (बी [के + 1] - बी [के])।

इसी प्रकार एस _के के अंतिम एन-के -1 शर्तों के लिए।

जब से हम एस , टी , और यू गणना कर सकता है रैखिक समय में, और हम लगातार समय में _{k + 1} एस के एस _{कश्मीर} से जा सकते हैं, हम गणना कर सकते हैं रैखिक समय में सभी एस _के। तो ऐसा करें, सबसे छोटा याद रखें, और आप कर चुके हैं।

मूल सरणी के लिए k प्राप्त करने के लिए क्रम क्रमपरिवर्तन के विपरीत का उपयोग करें।

Answer 3

यहां ओ (एनएलओएनएन) समाधान है। उदाहरण

A 6 2 5 10 3 8 7 
B 1 5 4 3 6 9 7 

1) सबसे पहले प्रकार बी ए के तत्व के आदेश की बढ़ती करने के लिए दो सरणी सिर्फ बी साथ बाध्यकारी है प्रकार के बाद, हम

A 6 10 5 2 3 7 
B 1 3 4 5 6 7 

प्राप्त बी के बाद से क्रम में अब कर रहे हैं । हम

n-1 
sum A[i]|B[i]-B[k]| 
i=0 

k-1     n-1 
=sum A[i](B[k]-B[i])+ sum A[i](B[k]-B[i]) 
i=0     i=k+1 
     k-1  n-1   k-1   n-1 
=B[k](sum A[i] -sum A[i]) - (sum A[i]B[i]- sum A[i]B[i]) 
     i=0  i=k+1  i=0   i=k+1 

2) हम सरणी एक सुमा का उपसर्ग योग की गणना 0 6 16 21 23 26 33

  i=e 
With sumA sum A[i] can be calcuated in O(1) time for any s and e. 
      i=s 

इसी कारण है =, हम एक [i] बी गणना कर सकते हैं [i] उपसर्ग राशि। तो प्रत्येक के लिए, इसके मूल्य की जांच करने के लिए, यह केवल ओ (1) समय लेता है। तो कुल समय जटिलता O(NlogN)+O(N).