आसन्न तत्व

Question

पर मूल्य स्थानांतरित करके किसी सरणी को किसी सरणी में बदलें, मुझे 2 सरणी, इनपुट और आउटपुट ऐरे दिया गया है। लक्ष्य इनपुट सरणी को आउटपुट सरणी में 1 मान के स्थानांतरण को अपने आसन्न तत्व में दिए गए चरण में स्थानांतरित करना है। उदाहरण: इनपुट सरणी [0,0,8,0,0] है और आउटपुट सरणी [2,0,4,0,2] है। यहां पहला कदम [0,1,7,0,0] होगा और दूसरा चरण [0,1,6,1,0] होगा और इसी तरह।

कुशलता से ऐसा करने के लिए एल्गोरिदम क्या हो सकता है? मैं बीएफएस करने की सोच रहा था लेकिन फिर हमें प्रत्येक तत्व से बीएफएस करना है और यह घातीय हो सकता है। क्या कोई इस समस्या के समाधान का सुझाव दे सकता है?

Answer 1

मुझे लगता है कि बीएफएस वास्तव में काम कर सकता है।

नोटिस कि n*O(n+m) = O(n^2+nm) और इसलिए घातीय नहीं है।

भी आप इस्तेमाल कर सकते हैं: फ्लोयड-Warshall एल्गोरिथ्म और जॉनसन एल्गोरिथ्म, एक "फ्लैट" ग्राफ के लिए 1 के एक वजन के साथ, या यहाँ तक कि उनके वास्तविक दूरी के अनुसार एक नए तरीके से कोने से कनेक्ट करने और संभावित रूप से कुछ पुनरावृत्तियों सहेजें।

आशा है कि यह मदद की :)

Answer 2

एक साधारण लालची एल्गोरिथ्म काम करते हैं और चरणों की न्यूनतम संख्या में काम करेगा। फ़ंक्शन कार्य के लिए आवश्यक चरणों की कुल संख्या देता है।

int shift(std::vector<int>& a,std::vector<int>& b){ 

    int n = a.size(); 

    int sum1=0,sum2=0; 
    for (int i = 0; i < n; ++i){ 
     sum1+=a[i]; 
     sum2+=b[i]; 
    } 

    if (sum1!=sum2) 
    { 
     return -1; 
    } 

    int operations=0; 
    int j=0; 
    for (int i = 0; i < n;) 
    { 
     if (a[i]<b[i]) 
     { 
      while(j<n and a[j]==0){ 
       j++; 
      } 
      if(a[j]<b[i]-a[i]){ 
       operations+=(j-i)*a[j]; 
       a[i]+=a[j]; 
       a[j]=0; 
      }else{ 
       operations+=(j-i)*(b[i]-a[i]); 
       a[j]-=(b[i]-a[i]); 
       a[i]=b[i]; 
      } 
     }else if (a[i]>b[i]) 
     { 
      a[i+1]+=(a[i]-b[i]); 
      operations+=(a[i]-b[i]); 
      a[i]=b[i]; 
     }else{ 
      i++; 
     } 
    } 

    return operations; 
} 

यहाँ -1 एक विशेष मूल्य जिसका अर्थ है कि यह देखते हुए सरणी वांछित में बदला नहीं जा सकता है।

समय जटिलता: ओ (एन)।

Answer 3

मुझे लगता है कि आप बस वर्तमान सरणी में प्रत्येक दिशा में स्कैनिंग संचयी मूल्य (उस दिशा में) पर नज़र रखने और वांछित आउटपुट सरणी और आप के आगे के रूप में आवश्यक के साथ मूल्यों धक्का द्वारा यह कर सकते हैं:

scan from the left looking for first cell where 
    cumulative value > cumulative value in desired output 
while that holds move 1 from that cell to the next cell to the right 

scan from the right looking for first cell where 
    cumulative value > cumulative value in desired output 
while that holds move 1 from that cell to the next cell to the left 

अपने उदाहरण के लिए चरणों का होगा:

FWD: [0,0,8,0,0] [0,0,7,1,0] [0,0,6,2, 0] [0,0,6,1,1] [0,0,6,0,2]

आरईवी: [0,1,5,0,2] [0,2,4,0,2] [1,1,4,0,2] [2,0,4,0 , 2]

Answer 4

void transform(int[] in, int[] out, int size) 
{ 
    int[] state = in.clone(); 

    report(state); 

    while (true) 
    { 
     int minPressure = 0; 
     int indexOfMinPressure = 0; 

     int maxPressure = 0; 
     int indexOfMaxPressure = 0; 

     int pressureSum = 0; 

     for (int index = 0; index < size - 1; ++index) 
     { 
      int lhsDiff = state[index] - out[index]; 
      int rhsDiff = state[index + 1] - out[index + 1]; 

      int pressure = lhsDiff - rhsDiff; 

      if (pressure < minPressure) 
      { 
       minPressure = pressure; 
       indexOfMinPressure = index; 
      } 

      if (pressure > maxPressure) 
      { 
       maxPressure = pressure; 
       indexOfMaxPressure = index; 
      } 

      pressureSum += pressure; 
     } 

     if (minPressure == 0 && maxPressure == 0) 
     { 
      break; 
     } 

     boolean shiftLeft; 

     if (Math.abs(minPressure) > Math.abs(maxPressure)) 
     { 
      shiftLeft = true; 
     } 
     else if (Math.abs(minPressure) < Math.abs(maxPressure)) 
     { 
      shiftLeft = false; 
     } 
     else 
     { 
      shiftLeft = (pressureSum < 0); 
     } 

     if (shiftLeft) 
     { 
      ++state[indexOfMinPressure]; 
      --state[indexOfMinPressure + 1]; 
     } 
     else 
     { 
      --state[indexOfMaxPressure]; 
      ++state[indexOfMaxPressure + 1]; 
     } 

     report(state); 
    } 
}