एक सरणी है: [१,१,१,१,२,३,४], सरणी में समान अंतर के सभी सेटों को गिनें एक सरणी में प्रत्येक सेट के लिए अंतर मान समान नहीं हो सकता है

Way to count one set have same difference:
-1,0,1  -> count = 1 with diff = 1
1,1,1   -> count = 1 with diff = 0
1,2,3,4 -> count = 3 with diff = 1 ([1,2,3],[1,2,3,4],[2,3,4])
0,1     -> not count
0,1,3   -> not count
0,1,1,2 -> not count , althought it has 0,1 and 1,2 with diff = 1 but it is not continous

As the above array  [1,1,1,1,2,3,4] count = 6
There are 6 sets has the same difference value:
 [1,1,1],[1,1,1,1],[1,1,1] with difference = 0
 [1,2,3],[1,2,3,4],[2,3,4] with difference = 1

यहाँ मेरा पाशविक बल दृष्टिकोण है O(n2) क्या मैं इसे और अधिक कुशलता से सुधारने के लिए याद रखने के साथ DP का उपयोग कर सकता हूँ?

 function run(pArray){
      var count = 0;
      var length = pArray.length;
      for(var i = 0;i<length - 2;i++){          
        var nextIdx = i + 1;
        var diff = pArray[nextIdx]-pArray[i];          
        while(true){
          nextIdx ++;
        
          if(nextIdx > length - 1){
            break;
          }    
          if(pArray[nextIdx] - pArray[nextIdx - 1] !== diff){
            break;
          }else{
            count ++;
          }
        }
    }
    
    console.log(count);
    }
    
    run([1,1,1,1,2,3,4]);
0
duhdh12 9 अक्टूबर 2018, 04:18

1 उत्तर

सबसे बढ़िया उत्तर

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

उस स्थिति में यह O(n) में किया जा सकता है।

विचार है:

यदि आप पाते हैं कि एक मिलान अंतर एक गणना चर में वृद्धि करता है, तो परिणाम को परिणाम = परिणाम + गणना के रूप में अपडेट करें।

एक उदाहरण लें [1,1,1,1]। आपको सूचकांक 0,1 पर विचार करने की आवश्यकता नहीं है।

इंडेक्स 2 लें देखें कि क्या arr[2] - arr[1] == arr[1] - arr[0] फिर 0 से 1 तक की वृद्धि की गणना करें, इसे परिणाम में जोड़ें।

अनुक्रमणिका ३ लें देखें कि क्या arr[3] - arr[2] == arr[2] - arr[1] , हाँ यह बराबर है, फिर 2 पर वृद्धि की गणना करें, इसे परिणाम में जोड़ें। अब परिणाम = 1 + 2 = 3।

आपको यह विचार मिलता है, जब तक आपको ऐसे तत्व मिलते हैं जो मानदंड को पूरा करते हैं arr[i] - arr[i-1] == arr[i-1] - arr[i-2] आप अगले उच्च मूल्य को जोड़ते रहते हैं। तो परिणाम = 1 + 2 + 3 +....i-2 और इसी तरह दिए गए सूचकांक के लिए i

यदि आपको मिलान अंतर नहीं मिलता है, तो गणना चर को शून्य पर रीसेट करें और नए सिरे से शुरू करें।

नोट: मैं जावास्क्रिप्ट से उतना परिचित नहीं हूं, लेकिन ऐसा लगता है:

<div>
    <script>
      function countSets(arr) {
        if (arr === undefined || arr.length < 3) return 0;
        let count = 0;
        let res = 0;
        for (let i = 2; i < arr.length; ++i) {
          if (arr[i] - arr[i - 1] === arr[i - 1] - arr[i - 2]) {
            count++;
          } else {
            count = 0;
          }
          res += count;
        }
        return res;
      }
      console.log("[1, 1, 1] -> " + countSets([1, 1, 1]))
      console.log("[1, 1, 1, 2, 2, 2] -> " + countSets([1, 1, 1, 2, 2, 2]))
      console.log("[1, 1, 1, 2, 3, 4] -> " + countSets([1, 1, 1, 2, 3, 4]))
      console.log("[1, 1, 2, 3, 4, 4, 5, 5] -> " + countSets([1, 1, 2, 3, 4, 4, 5, 5]))
      console.log("[1, 1, 1, 2, 3, 4, 5, 6] -> " + countSets([1, 1, 1, 2, 3, 4, 5, 6]))
      console.log("[1, 2, 1, 2, 1] -> " + countSets([1, 2, 1, 2, 1]))
    </script>
</div>
0
SomeDude 10 अक्टूबर 2018, 04:41