दिलचस्प पोस्ट
पूर्ण बेस्ड लाइन और रिकवरीकेस यूसीएम में वृद्धिशील बेसलाइन के बीच अंतर क्या है? SQL सर्वर: कुछ दिनों के लिए कोई डेटा मौजूद नहीं है, तो किसी तिथि सीमा में सभी दिनों का चयन कैसे करें ViewPager का उपयोग करने वाले एक टुकड़े पर Google मानचित्र V2 को कैसे रखा जाए कोणीय विंडो रीसाइज इवेंट शीर्ष पंक्ति कोशिकाओं को समन्वित करें यदि स्तंभ के नीचे 1 है क्यों "$ ()। तैयार (हैंडलर)" की सिफारिश नहीं की जाती है? एंड्रॉइड में स्थान श्रोता के साथ पृष्ठभूमि सेवा सी # में "स्थिर विधि" क्या है? क्रोम में वेबकिट-रूपांतरण के साथ घूर्णन करते समय वोंगकी पाठ एंटी-एलिआसिंग सरल एक्सएमएल – नोड्स में कॉलन से निपटना पायथन इमेजिंग पुस्तकालय (पीआईएल) के साथ, एक छवि को एक अन्य छवि पर एक अल्फा चैनल के साथ कैसे तैयार किया जाता है? एएसपी.नेट में बहु-चयन ड्रॉपडाउन सूची किसी अन्य EL अभिव्यक्ति में एक EL अभिव्यक्ति में घोंसला कैसे करें Node.js पर HTML- पार्सर निजी बाइट, वर्चुअल बाइट्स, काम सेट क्या है?

संख्याओं की एक सरणी को देखते हुए, अन्य सभी संख्याओं के उत्पादों की वापसी की श्रेणी (कोई विभाजन नहीं)

मुझे नौकरी की साक्षात्कार में यह सवाल पूछा गया था, और मैं यह जानना चाहूंगा कि दूसरों ने इसे कैसे हल किया होगा। मैं जावा के साथ सबसे अधिक आरामदायक हूँ, लेकिन अन्य भाषाओं में समाधान स्वागत है

संख्याओं की एक सरणी को देखते हुए, संख्याओं के एक सरणी को वापस लौटाते products , जहां products[i] सभी nums[j], j != i

 Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] 

आपको विभाजन के बिना O(N) में ऐसा करना चाहिए।

Solutions Collecting From Web of "संख्याओं की एक सरणी को देखते हुए, अन्य सभी संख्याओं के उत्पादों की वापसी की श्रेणी (कोई विभाजन नहीं)"

पॉलीगेनेलब्रीकेंट्स विधि का एक स्पष्टीकरण है: चाल के लिए arrays (4 तत्वों के मामले में) का निर्माण करना है

 { 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], } { a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, } 

दोनों को क्रमशः बाएं और दाएं किनारों पर शुरू करके ओ (एन) में किया जा सकता है।

फिर तत्व द्वारा दो सरणियों तत्व को गुणा करना आवश्यक परिणाम देता है

मेरा कोड ऐसा कुछ दिखाई देगा:

 int a[N] // This is the input int products_below[N]; p=1; for(int i=0;i<N;++i) { products_below[i]=p; p*=a[i]; } int products_above[N]; p=1; for(int i=N-1;i>=0;--i) { products_above[i]=p; p*=a[i]; } int products[N]; // This is the result for(int i=0;i<N;++i) { products[i]=products_below[i]*products_above[i]; } 

यदि आपको अंतरिक्ष में हे (1) होना चाहिए, तो आप भी ऐसा कर सकते हैं (जो कम स्पष्ट IMHO है)

 int a[N] // This is the input int products[N]; // Get the products below the current index p=1; for(int i=0;i<N;++i) { products[i]=p; p*=a[i]; } // Get the products above the curent index p=1; for(int i=N-1;i>=0;--i) { products[i]*=p; p*=a[i]; } 

जगह में modoffication करने के लिए यहाँ एक छोटी पुनरावर्ती समारोह (सी ++ में) है इसके लिए ओ (एन) अतिरिक्त स्थान की आवश्यकता है (स्टैक पर) हालांकि। मान लें कि सरणी एक में है और एन में सरणी की लंबाई है, हमारे पास है

 int multiply(int *a, int fwdProduct, int indx) { int revProduct = 1; if (indx < N) { revProduct = multiply(a, fwdProduct*a[indx], indx+1); int cur = a[indx]; a[indx] = fwdProduct * revProduct; revProduct *= cur; } return revProduct; } 

जावा में इसे हल करने का मेरा पहला प्रयास है गैर-मानक स्वरूपण के लिए क्षमा चाहते हैं, लेकिन कोड में बहुत अधिक अनुलिपि है, और यह सबसे अच्छा मैं इसे पठनीय बनाने के लिए कर सकता हूं।

 import java.util.Arrays; public class Products { static int[] products(int... nums) { final int N = nums.length; int[] prods = new int[N]; Arrays.fill(prods, 1); for (int i = 0, pi = 1 , j = N-1, pj = 1 ; (i < N) && (j >= 0) ; pi *= nums[i++] , pj *= nums[j--] ) { prods[i] *= pi ; prods[j] *= pj ; } return prods; } public static void main(String[] args) { System.out.println( Arrays.toString(products(1, 2, 3, 4, 5)) ); // prints "[120, 60, 40, 30, 24]" } } 

लूप pi = nums[0] * nums[1] *.. nums[i-1] और pj = nums[N-1] * nums[N-2] *.. nums[j+1] । बाईं तरफ i भाग "उपसर्ग" तर्क है, और दाईं तरफ j भाग "प्रत्यय" तर्क है।


पुनरावर्ती एक-लाइनर

जसमीत ने एक (सुंदर!) पुनरावर्ती समाधान दिया; मैंने इसे (घृणित!) जावा एक-लाइनर में बदल दिया है। यह रिक्त स्थान में O(N) अस्थायी स्थान के साथ साथ संशोधन करता है

 static int multiply(int[] nums, int p, int n) { return (n == nums.length) ? 1 : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1)) + 0*(nums[n] *= p); } int[] arr = {1,2,3,4,5}; multiply(arr, 1, 0); System.out.println(Arrays.toString(arr)); // prints "[120, 60, 40, 30, 24]" 

हास्केल में माइकल एंडरसन के समाधान का अनुवाद करना:

 otherProducts xs = zipWith (*) below above where below = scanl (*) 1 $ init xs above = tail $ scanr (*) 1 xs 

चुपके से "कोई विभाजन नहीं" नियम circumventing:

 sum = 0.0 for i in range(a): sum += log(a[i]) for i in range(a): output[i] = exp(sum - log(a[i])) 

हे (ओ) (एन) जटिलता के साथ यहां सरल और साफ समाधान प्राप्त करते हैं:

 int[] a = {1,2,3,4,5}; int[] r = new int[a.length]; int x = 1; r[0] = 1; for (int i=1;i<a.length;i++){ r[i]=r[i-1]*a[i-1]; } for (int i=a.length-1;i>0;i--){ x=x*a[i]; r[i-1]=x*r[i-1]; } for (int i=0;i<r.length;i++){ System.out.println(r[i]); } 

सी ++, ओ (एन):

 long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>()); transform(in.begin(), in.end(), back_inserter(res), bind1st(divides<long long>(), prod)); 

यह ओ (एन ^ 2) है, लेकिन एफ # बहुत ही सुंदर है:

 List.fold (fun seed i -> List.mapi (fun jx -> if i=j+1 then x else x*i) seed) [1;1;1;1;1] [1..5] 

यहाँ आधुनिक समाधान में मेरा समाधान है C ++ यह std::transform का उपयोग करता है और याद रखना बहुत आसान है

ऑनलाइन कोड (वंडबॉक्स)

 #include<algorithm> #include<iostream> #include<vector> using namespace std; vector<int>& multiply_up(vector<int>& v){ v.insert(v.begin(),1); transform(v.begin()+1, v.end() ,v.begin() ,v.begin()+1 ,[](auto const& a, auto const& b) { return b*a; } ); v.pop_back(); return v; } int main() { vector<int> v = {1,2,3,4,5}; auto vr = v; reverse(vr.begin(),vr.end()); multiply_up(v); multiply_up(vr); reverse(vr.begin(),vr.end()); transform(v.begin(),v.end() ,vr.begin() ,v.begin() ,[](auto const& a, auto const& b) { return b*a; } ); for(auto& i: v) cout << i << " "; } 
  1. यात्रा वाम-> सही और उत्पाद को सहेजते रहें इसे अतीत कॉल करें -> हे (एन)
  2. यात्रा का अधिकार -> उत्पाद को छोड़ दें इसे भविष्य कहें -> हे (एन)
  3. परिणाम [i] = पिछले [i-1] * भविष्य [i + 1] -> ओ (एन)
  4. अतीत [-1] = 1; और भविष्य [एन + 1] = 1;

पर)

मुश्किल:

निम्न का उपयोग करें:

 public int[] calc(int[] params) { int[] left = new int[n-1] in[] right = new int[n-1] int fac1 = 1; int fac2 = 1; for( int i=0; i<n; i++ ) { fac1 = fac1 * params[i]; fac2 = fac2 * params[ni]; left[i] = fac1; right[i] = fac2; } fac = 1; int[] results = new int[n]; for( int i=0; i<n; i++ ) { results[i] = left[i] * right[i]; } 

हां, मुझे यकीन है कि मैं आई के बजाय कुछ i-1 को खो दिया है, लेकिन इसे हल करने का तरीका

वहाँ भी एक ओ (एन ^ (3/2)) गैर इष्टतम समाधान है। यह काफी दिलचस्प है, यद्यपि।

पहले आकार के प्रत्येक आंशिक गुणांक को पहली बार प्रसंस्करण करते हैं N ^ 0.5 (यह ओ (एन) समय की जटिलता में किया जाता है)। फिर, प्रत्येक संख्या के अन्य मूल्यों के लिए गणना- 2 * O (N ^ 0.5) समय में कई-बार किया जा सकता है (क्यों? क्योंकि आपको केवल दूसरे के अंतिम तत्व ((N ^ 0.5) – 1) नंबर की आवश्यकता होती है, और परिणाम ((N ^ 0.5) – 1) संख्या जो वर्तमान संख्या के समूह से संबंधित हैं, गुणा करें। प्रत्येक नंबर के लिए ऐसा करने से, एक ओ (एन ^ (3/2)) समय प्राप्त कर सकता है।

उदाहरण:

4 6 7 2 3 1 9 5 8

आंशिक परिणाम: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

3 के मान की गणना के लिए, एक को दूसरे समूहों के मूल्यों को 168 * 360 के गुणा करना होगा, और फिर 2 * 1 के साथ

 public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int[] result = { 1, 1, 1, 1, 1 }; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < i; j++) { result[i] *= arr[j]; } for (int k = arr.length - 1; k > i; k--) { result[i] *= arr[k]; } } for (int i : result) { System.out.println(i); } } 

मैं इस समाधान के साथ आया था और मैं इसे इतना स्पष्ट तुम्हें क्या लगता है !?

 def productify(arr, prod, i): if i < len(arr): prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1) retval = productify(arr, prod, i + 1) prod[i] *= retval return retval * arr[i] return 1 

arr = [1, 2, 3, 4, 5] उत्पाद = [] उत्पादकता (arr, prod, 0) प्रिंट उत्पाद

खैर, इस समाधान को सी / सी ++ का माना जा सकता है चलिए कहते हैं कि हमारे पास "ए" वाले एक तत्व हैं, जैसे [एन], तो छद्म कोड नीचे होगा

 for(j=0;j<n;j++) { prod[j]=1; for (i=0;i<n;i++) { if(i==j) continue; else prod[j]=prod[j]*a[i]; } 

एक और समाधान, विभाजन का उपयोग करना। दो बार ट्रवर्सल के साथ सभी तत्वों को गुणा करें और फिर इसे प्रत्येक तत्व द्वारा विभाजित करना शुरू करें।

 {-
 पुनरावर्ती समाधान sqrt (n) सबसेट का उपयोग करते हुए  ओ (एन) में चलाता है

 आवर्ती रूप से sqrt (n) आकार sqrt (n) के उपसमुच्चय पर समाधान की गणना करता है 
 फिर प्रत्येक उपशीर्षक के उत्पाद योग पर पुनरावर्ती।
 फिर प्रत्येक सबसेट में प्रत्येक तत्व के लिए, यह उत्पाद को इसके साथ गणना करता है
 अन्य सभी उत्पादों का उत्पाद योग
 फिर सभी सबसेट्स को चपटे।

 रन समय पर पुनरावृत्ति टी (एन) = sqrt (n) * टी (sqrt (n)) + टी (sqrt (n)) + n

 मान लीजिए कि टी (एन) ≤ सी एन ओ (एन) में

 टी (एन) = sqrt (n) * टी (sqrt (n)) + टी (sqrt (n)) + n
     ≤ sqrt (n) * c * sqrt (n) + c * sqrt (n) + n
     ≤ c * n + c * sqrt (n) + n
     ≤ (2 सी + 1) * n
     और;  पर)

 ध्यान दें कि छत (sqrt (n)) को द्विआधारी खोज का उपयोग करके गणना किया जा सकता है 
 और हे (लॉगन) पुनरावृत्तियों, यदि sqrt अनुदेश की अनुमति नहीं है।
 -}

 अन्य प्रॉडक्ट्स [] = []
 अन्य उत्पादों [x] = [1]
 अन्य उत्पाद [x, y] = [y, x]
 अन्य प्रोडक्ट्स ए = गुड़िया '(++) [] $ zipWith (\ sp -> नक्शा (* p) s) solvedSubsets subsetOtherProducts
     कहा पे 
       n = लंबाई a

       - सबसेट आकार  आवश्यकता है कि 1 <s <n
       s = छत $ sqrt $ से इनटेग्राल n

       solvedSubsets = नक्शा अन्य उत्पाद उपगों
       सबसेटऑपरप्रोडक्ट्स = अन्य प्रोडक्ट्स $ मैप उत्पाद सबसेट्स

       सबसेट = रिवर्स $ पाश ए []
           जहां लूप [] acc = एसीसी
                 लूप ए एसीसी = लूप (ड्रॉप सा) ((ले लें): एसीसी)

यहां मेरा कोड है:

 int multiply(int a[],int n,int nextproduct,int i) { int prevproduct=1; if(i>=n) return prevproduct; prevproduct=multiply(a,n,nextproduct*a[i],i+1); printf(" i=%d > %d\n",i,prevproduct*nextproduct); return prevproduct*a[i]; } int main() { int a[]={2,4,1,3,5}; multiply(a,5,1,0); return 0; } 

सी # का उपयोग करते हुए, यहाँ एक थोड़ा कार्यात्मक उदाहरण है:

  Func<long>[] backwards = new Func<long>[input.Length]; Func<long>[] forwards = new Func<long>[input.Length]; for (int i = 0; i < input.Length; ++i) { var localIndex = i; backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex]; forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex]; } var output = new long[input.Length]; for (int i = 0; i < input.Length; ++i) { if (0 == i) { output[i] = forwards[i + 1](); } else if (input.Length - 1 == i) { output[i] = backwards[i - 1](); } else { output[i] = forwards[i + 1]() * backwards[i - 1](); } } 

मैं पूरी तरह निश्चित नहीं हूं कि यह ओ (एन) है, निर्मित फ़नक्स के अर्ध-रिकर्सन के कारण, लेकिन मेरे परीक्षण यह संकेत देते हैं कि यह समय में ओ (एन) है

संख्याओं के उत्पाद को बाएं और प्रत्येक तत्व के दायीं तरजीह से पहले करना। हर तत्व के लिए वांछित मूल्य उसके उत्पाद के उत्पाद है।

 #include <stdio.h> unsigned array[5] = { 1,2,3,4,5}; int main(void) { unsigned idx; unsigned left[5] , right[5]; left[0] = 1; right[4] = 1; /* calculate products of numbers to the left of [idx] */ for (idx=1; idx < 5; idx++) { left[idx] = left[idx-1] * array[idx-1]; } /* calculate products of numbers to the right of [idx] */ for (idx=4; idx-- > 0; ) { right[idx] = right[idx+1] * array[idx+1]; } for (idx=0; idx <5 ; idx++) { printf("[%u] Product(%u*%u) = %u\n" , idx, left[idx] , right[idx] , left[idx] * right[idx] ); } return 0; } 

परिणाम:

 $ ./a.out [0] Product(1*120) = 120 [1] Product(1*60) = 60 [2] Product(2*20) = 40 [3] Product(6*5) = 30 [4] Product(24*1) = 24 

(अपडेट करें: अब मैं करीब से देख रहा हूं, यह माइकल एंडरसन, डैनियल मिगोवस्की और पॉलीगेंज़ेबल्युब्रिकेंट जैसी ही विधि का उपयोग करता है)

यहाँ पूरा करने के लिए Scala में कोड है:

 val list1 = List(1, 2, 3, 4, 5) for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_)) 

यह निम्न का प्रिंट होगा:

 120 60 40 30 24 

कार्यक्रम वर्तमान elem (_! = Elem) को फ़िल्टर करेगा; और कम से कम लिफ़्ट विधि के साथ नई सूची का गुणा करें। मुझे लगता है कि यह ओ (एन) होगा यदि आप स्केल दृश्य या आलसी eval के लिए Iterator का उपयोग करें।

// यह जरूरी में पुनरावर्ती समाधान / मुख्य उत्पाद (ए, 1,0) से निम्नलिखित के रूप में बुलाया गया है;

 public static double product(double[] a, double fwdprod, int index){ double revprod = 1; if (index < a.length){ revprod = product2(a, fwdprod*a[index], index+1); double cur = a[index]; a[index] = fwdprod * revprod; revprod *= cur; } return revprod; } 

ओ (एन) रनटाइम के साथ एक साफ समाधान:

  1. प्रत्येक तत्व के लिए सभी तत्वों के उत्पाद की गणना करता है जो इससे पहले होती हैं और यह एक सरणी "पूर्व" में संग्रहीत करता है।
  2. प्रत्येक तत्व के लिए उस तत्व के बाद होने वाले सभी तत्वों के उत्पाद की गणना करें और उसे "पोस्ट" में संग्रहित करें
  3. एक तत्व के लिए एक अंतिम सरणी "परिणाम" बनाएं, I,

     result[i] = pre[i-1]*post[i+1]; 
 function solution($array) { $result = []; foreach($array as $key => $value){ $copyOfOriginalArray = $array; unset($copyOfOriginalArray[$key]); $result[$key] = multiplyAllElemets($copyOfOriginalArray); } return $result; } /** * multiplies all elements of array * @param $array * @return int */ function multiplyAllElemets($array){ $result = 1; foreach($array as $element){ $result *= $element; } return $result; } $array = [1, 9, 2, 7]; print_r(solution($array)); 

इसे इस्तेमाल करे!

 import java.util.*; class arrProduct { public static void main(String args[]) { //getting the size of the array Scanner s = new Scanner(System.in); int noe = s.nextInt(); int out[]=new int[noe]; int arr[] = new int[noe]; // getting the input array for(int k=0;k<noe;k++) { arr[k]=s.nextInt(); } int val1 = 1,val2=1; for(int i=0;i<noe;i++) { int res=1; for(int j=1;j<noe;j++) { if((i+j)>(noe-1)) { int diff = (i+j)-(noe); if(arr[diff]!=0) { res = res * arr[diff]; } } else { if(arr[i+j]!=0) { res= res*arr[i+j]; } } out[i]=res; } } //printing result System.out.print("Array of Product: ["); for(int l=0;l<out.length;l++) { if(l!=out.length-1) { System.out.print(out[l]+","); } else { System.out.print(out[l]); } } System.out.print("]"); } } 

यहां एक और सरल अवधारणा है जो O(N) में समस्या को हल करती है।

  int[] arr = new int[] {1, 2, 3, 4, 5}; int[] outArray = new int[arr.length]; for(int i=0;i<arr.length;i++){ int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b); outArray[i] = res/arr[i]; } System.out.println(Arrays.toString(outArray)); 

हम पहले सूची से nums[j] (जहां j != i ) को बाहर कर सकते हैं, तो बाकी का उत्पाद प्राप्त करें; निम्नलिखित इस पहेली को हल करने का एक python way है:

 def products(nums): return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ] print products([1, 2, 3, 4, 5]) [out] [120, 60, 40, 30, 24] 

बिलज़ के उत्तर के आधार पर – क्षमा करें, मैं टिप्पणी नहीं कर सकता, लेकिन यहां एक स्काला संस्करण है जो सूची में डुप्लिकेट आइटम को ठीक से संभालता है, और शायद ओ (एन) है:

 val list1 = List(1, 7, 3, 3, 4, 4) val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)} view.force 

रिटर्न:

 List(1008, 144, 336, 336, 252, 252) 

मेरे पास O(n) स्पेस और O(n^2) समय जटिलता के साथ एक समाधान है,

 public static int[] findEachElementAsProduct1(final int[] arr) { int len = arr.length; // int[] product = new int[len]; // Arrays.fill(product, 1); int[] product = IntStream.generate(() -> 1).limit(len).toArray(); for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (i == j) { continue; } product[i] *= arr[j]; } } return product; } 
  int[] arr1 = { 1, 2, 3, 4, 5 }; int[] product = new int[arr1.Length]; for (int i = 0; i < arr1.Length; i++) { for (int j = 0; j < product.Length; j++) { if (i != j) { product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i]; } } }