एक सरणी में शेष बिंदु ढूँढना

Question

यह प्रश्न एक महान यूट्यूब चैनल से है, जो साक्षात्कार में पूछे जा सकने वाली समस्याओं को दे रहा है।

यह मूल रूप से एक सरणी में शेष बिंदु खोजने के लिए संबंधित है। सबसे अच्छी व्याख्या करने के लिए यहां एक उदाहरण दिया गया है; {1,2,9,4, -1}। यहां से योग (1 + 2) = योग (4 + (- 1)) 9 शेष बिंदु बना रहा है। उत्तर की जांच किए बिना मैंने यह पूछने से पहले एल्गोरिदम लागू करने का निर्णय लिया है कि एक और अधिक कुशल दृष्टिकोण किया जा सकता है;

1. योग सभी सरणी में तत्वों हे (एन)
2. राशि का आधा जाओ हे (1)
3. प्रारंभ स्कैनिंग सरणी, बाएं से, और रोक जब sumleft सामान्य राशि के आधे से बड़ा है। ओ (एन)
4. योग सही प्राप्त करने के लिए, दाईं ओर के लिए ऐसा ही करें।ओ (एन)।
5. तो sumleftsumright वापसी आगमन के बराबर है [आकार/2] अन्य सभी-1

क्योंकि इस समाधान बिना किसी प्रयास के मेरे सिर में पॉप मैं पूछ रहा हूँ लौटने के लिए, उपलब्ध कराने के ओ (एन) चलने का समय। क्या यह समाधान, यदि सत्य है, तो विकसित किया जा सकता है या यदि कोई वैकल्पिक तरीका सही नहीं है?

Answer 1

आपका एल्गोरिथ्म (जवाबी उदाहरण: 1 -1 1 0 1 -1 1) अच्छा नहीं है, अच्छा समाधान अपने सरणी के एक आंशिक योग की गणना करने के लिए है (ताकि आप sumleft और ओ में sumright गणना कर सकता है कर सकते हैं (1) सरणी की प्रत्येक कोशिका के लिए) और फिर (या एक ही समय में यदि आप पहले से ही वैश्विक योग जानते हैं) अपने सरणी में एक सेल जैसे sumleft = sumright जो ओ (एन) है।

वैश्विक कम्प्यूटिंग:

A=[5,2,3,1,4,6] 
partial sum = [5,7,10,11,15,21] 

इस सरणी आप गणना कर सकता है sumleft[i]=partial_sum[i-1] और sumright[i]=partial_sum[n-1]-partial_sum[i]

सुधार के साथ

:

सरणी A के एक आंशिक योग

[A[0], A[0]+A[1], A[0]+A[1]+A[2], …, A[0]+A[1]+A[2]+…+A[n-1]] 

उदाहरण है पहले और फिर योग वर्तमान इंडेक्स के लिए केवल आंशिक योग आपको ओ (एन) अतिरिक्त स्थान के बजाय केवल ओ (1) अतिरिक्त स्थान का उपयोग करने में सक्षम बनाता है यदि आप सभी partial_sum सरणी को स्टोर करते हैं।

Answer 2

मेरे पास वास्तव में 2 प्रारंभ बिंदु होंगे, एक बाएं बिंदु (बाएं लॉक) पर, और एक दाएं सबसे अधिक बिंदु (दाएं स्थान) पर। एक sumLeft और sumRight संख्या पकड़ो।

leftLoc = 0; 
rightLoc = (n - 1); 
sumRight = array[rightLoc]; 
sumLeft = array[leftLoc]; 

while(leftLoc < rightLoc){ 
    if(sumRight > sumLeft){ 
     leftLoc++; 
     sumLeft += array[leftLoc]; 
    }else{ 
     rightLoc--; 
     sumRight += array[rightLoc]; 
    } 
} 

if((sumRight + array[rightLoc - 1]) == sumLeft){ 
    return rightLoc--; 
}else if((sumLeft + array[leftLoc + 1]) == sumRight){ 
    return leftLoc++; 
}else{ 
    // return floating point number location in the middle of the 2 locations 
} 

सभी जबकि कुल कितने पदों का ट्रैक रखने स्थानांतरित कर दिया गया हे (एन)

हो सकता है कि अपने संतुलन बिंदु अंतिम अंक के बीच में एक चल बिन्दु संख्या (है एक बार वे एक दूसरे के बगल में पूर्णांक स्थानों पर हैं)।

यह भी नकारात्मक संख्या उदाहरण के साथ काम करना चाहिए। शायद मुझे कुछ बढ़िया अनाज का विवरण याद आ रहा है, लेकिन इस विषय पर कुछ भिन्नता के परिणामस्वरूप आपको ओ (एन) रनटाइम एल्गोरिदम में परिणाम होना चाहिए।

Answer 3

मूल रूप से पहले सभी संख्याएं जोड़ें। यह एक ओ (एन) ऑपरेशन होगा। फिर सरणी की शुरुआत से शुरू होने वाले समय में सरणी से एक तत्व को upper == lower तक घटाएं। इस प्रकार कुल आदेश ओ (एन) होगा।

int BalancePoint(int a[], int begin, int end) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1 
{ 
    if(!a) return -1; 
    else if(begin == end) return begin; 

     long long upper = 0; 
     long long lower = 0; 

    for(int i = begin; i <= end; ++i) 
    { 
     upper += *(a+i); 
    } 

    for(int j = begin; j <= end; ++j) 
    { 
     upper -= *(a+j); 
     if(upper == lower) return j; 
     lower += *(a+j); 
    } 
    return -1; 
} 

एसटीएल का उपयोग

int BalancePointSTL(const vector<int> &A) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1 
{ 
    if(A.empty()) return -1; 

     long long upper = 0; 
     long long lower = 0; 

    for(unsigned int i = 0; i <= A.size(); ++i) 
    { 
     upper += A[i]; 
    } 

    for(unsigned int j = 0; j < A.size(); ++j) 
    { 
     upper -= A[j]; 
     if(upper == lower) return j; 
     lower += A[j]; 
    } 
    return -1; 
    } 

निम्नलिखित एक बेहतर प्रदर्शन सबसे खराब स्थिति है, लेकिन कुछ और if-else तुलना

int BalancePoint2(int a[], int begin, int end) // Better worst case senario by factor of 2 
{ 
    if(!a) return -1; 
    else if(begin == end) return begin; 

     long long upper = 0; 
     long long lower = 0; 

     int mid = (end-begin)/2; 

     for(int i = begin; i < mid; ++i) 
     { 
      lower += *(a+i); 
     } 
     for(int i = mid+1; i <= end; ++i) 
     { 
      upper += *(a+i); 
     } 

     if(upper == lower) return mid; 
     else if(lower < upper) 
     { 
      lower += *(a+mid); 
      for(int i= mid + 1 ; i <= end ; ++i) 
      { 
       upper -= *(a + i); 
       if(upper == lower) return i; 
       lower += *(a + i); 
      } 
     } 
     else { 
      upper += *(a + mid); 
      for(int i = mid - 1; i >=begin; --i) 
      { 
       lower -= *(a + i); 
       if(upper == lower) return i; 
       upper += *(a + i); 
      } 
     } 
     return -1; 
} 

Answer 4

मेरा मानना ​​है कि आप Center of Mass लिए देख रहे हैं के लिए होता है, यहाँ एक है गो में लिखा गया समाधान:

func centerOfGravity(a []int) float64 { 
    tot := 0.0 
    mass := 0.0 
    for i := range a { 
    tot += float64(i) * float64(a[i]) 
    mass += float64(a[i]) 
    } 
    return tot/mass 
} 

यह आपको 0-आधारित सरणी मानते हुए सरणी में द्रव्यमान के केंद्र का सूचकांक देता है। यह एक गैर-पूर्णांक परिणाम लौटा सकता है क्योंकि द्रव्यमान केंद्र सरणी की सीमा में कहीं भी हो सकता है।

Answer 5

आप सेंट्रॉइड या द्रव्यमान के केंद्र की तलाश में हैं। शुद्ध पायथन में:

def centroid(input_list): 
    idx_val_sum = 0.0 
    val_sum = 0.0 
    for idx,val in enumerate(input_list): 
     idx_val_sum += idx*val 
     val_sum += val 
    return idx_val_sum/float(val_sum) 

यह हे (एन) और यदि गैर पूर्णांक परिणाम बीमार का गठन कर रहे हैं, तो आप उन्हें एक सापेक्ष चेक के साथ अस्वीकार कर सकते हैं:

def integer_centroid(input_list): 
    idx_val_sum = 0.0 
    val_sum = 0.0 
    for idx,val in enumerate(input_list): 
     idx_val_sum += idx*val 
     val_sum += val 
    out = idx_val_sum/float(val_sum) 
    if out%1.0==0.0: 
     return out 
    else: 
     raise ValueError("Input list has non-integer centorid.") 

इस पोस्ट में किया जाना चाहिए था 14 जून 2012 की टिप्पणी तुरही के जवाब में एक टिप्पणी है, लेकिन मेरे पास पर्याप्त प्रतिष्ठा नहीं है। "ऑर्डर" को idx_val_sum में स्पष्ट रूप से ट्रैक किया गया है, जो मूल्य द्वारा भारित संचयी स्थिति योग है।

संपादित करें:

मैट, आप अपने अवलोकन के लिए धन्यवाद देता हूं। मुझे लगता है कि यह एक छद्म कोड था, लेकिन अब मैं सी ++ टैग देखता हूं। टिप्पणियों के साथ यहां कुछ (अनचाहे) सी ++ है।

एक सहज उदाहरण एक सरल लीवर हाथ समस्या है: अगर आप दो बलों f1 और f2 पदों x1 और x2 पर उस पर काम के साथ एक लीवर है, तो आप द्वारा घूर्णन से प्रणाली को रोका जा सकता स्थिति (एफ 1 * x1 + एफ 2 * x2)/(एफ 1 + एफ 2) पर बल लागू करना।एक निरंतर प्रणाली को x और एफ के उत्पाद पर एकीकरण की आवश्यकता होती है, लेकिन इस समस्या के लिए अलग-अलग स्थानों और बलों के साथ लीवर एक अच्छा सादृश्य हैं।

// untested code: 

float centroid(float * vec, int vec_length){ 

    float idx_val_sum = 0.0; 
    float val_sum = 0.0; 

    for (idx = 0; idx < vec_length; idx++){ 

    // keep a running sum of the product of the index and the value 
    idx_val_sum += float(idx)*vec[idx]; 

    // similarly, keep a running sum of the index 
    val_sum += vec[idx]; 

    } 
    // return the quotient of the product-sum and the index sum: 
    return idx_val_sum/val_sum; 
}