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

मैं नीचे क्या कर रहा हूं, मैं प्रत्येक नेस्टेड लूप में समान सूचकांकों के माध्यम से पुनरावृत्ति को समाप्त करते हुए संख्याओं के सभी संयोजनों के माध्यम से पुनरावृत्ति कर रहा हूं और मैं जांच रहा हूं कि आंतरिक लूप में तीन संख्याएं शून्य तक जुड़ती हैं या नहीं। यदि हां, तो मैं सरणी को एक स्ट्रिंग में परिवर्तित कर रहा हूं और यदि स्ट्रिंग पहले से परिणाम सरणी में नहीं है तो मैं इसे जोड़ रहा हूं। लौटने से ठीक पहले मैं स्ट्रिंग्स को वापस एक सरणी में परिवर्तित कर रहा हूं।

मैं इस बारे में किसी भी सुझाव की सराहना करता हूं कि इसे और कैसे अनुकूलित किया जाए या यदि मैं बेहतर तरीके से लागू करने के किसी अवसर से चूक गया। मैं कुल रिफैक्टर की तलाश नहीं कर रहा हूं, केवल कुछ समायोजन जो प्रदर्शन में सुधार करेंगे।

var threeSum = function(nums) {
    const sorted = nums.sort();

    if(sorted.length && (sorted[0] > 0 || sorted[sorted.length-1] < 0)) {
        return [];
    }

    let result = [];

    for(let i=0; i < sorted.length; i++) {
        for(let z=i+1; z < sorted.length; z++) {
            for(let q=z+1; q < sorted.length; q++) {
                if(sorted[i]+sorted[z]+sorted[q] === 0) {
                    const temp = [sorted[i], sorted[z], sorted[q]].join(',');

                    if(!result.includes(temp)) {
                        result.push(temp);
                    }
                }
            }
        }
    }

    return result.map(str => str.split(','));
};

नमूना इनपुट: [-1,0,1,2,-1,-4]

अपेक्षित आउटपुट: [[-1,-1,2],[-1,0,1]]

0
AnchovyLegend 7 जून 2020, 02:38
मानचित्र के लिए एक अच्छा उपयोग मामला प्रतीत होता है। Array#includes() का उपयोग करने की तुलना में लुक अप के लिए अधिक कुशल और स्ट्रिंग्स को वापस सरणियों में बदलने की आवश्यकता नहीं होगी। ऐसा भी लगता है कि शुरुआत में एक ही प्रकार प्रत्येक उप सरणी का एक प्रकार काट देगा
 – 
charlietfl
7 जून 2020, 02:50
@charlietfl, प्रतिक्रिया के लिए धन्यवाद, क्या आप अपने मतलब पर थोड़ा सा विस्तार कर सकते हैं? मैं इस मामले में मानचित्र का उपयोग कैसे कर सकता हूं और सरणी को समाप्त कर सकता हूं? सरणी में प्रत्येक तत्व पर केवल दिए गए फ़ंक्शन को मैप नहीं करता है, यह उसी फ़ंक्शन को कैसे पूरा करेगा जिसमें सरणी शामिल है?
 – 
AnchovyLegend
7 जून 2020, 02:53
आप Array#map() के बारे में सोच रहे हैं... मैं एक Map ऑब्जेक्ट
 – 
charlietfl
7 जून 2020, 02:54
हालांकि वह एक कुंजी के रूप में सरणी का उपयोग कर रहा है, इसलिए उसे अभी भी इसे क्रमबद्ध करने की आवश्यकता होगी
 – 
user120242
7 जून 2020, 02:58
ज़रूर... कुंजी के रूप में स्ट्रिंग करने के लिए सरणी में शामिल हों और सरणी को मान के रूप में संग्रहीत करें। फिर यह जांचना एक आसान myMap.has(joinedString) है कि यह मौजूद है या नहीं
 – 
charlietfl
7 जून 2020, 02:59

3 जवाब

एक स्पष्ट अनुकूलन तीसरे नेस्टेड लूप से ठीक पहले दो पहली संख्याओं के योग का पूर्व-गणना करना है। फिर तीसरे लूप में तुलना करें यदि वह संख्या तीसरी पुनरावृत्त संख्या के विपरीत है।

दूसरा अनुकूलन इस तथ्य का लाभ उठाना है कि आपके आइटम सॉर्ट किए गए हैं और तीसरे लूप के बजाय शेष सरणी में दो पहले शब्दों के योग के वास्तविक नकारात्मक के लिए बाइनरी खोज का उपयोग करें। यह दूसरा अनुकूलन O(N3) से O(N2LogN) तक जटिलता लाता है

जो तीसरे अनुकूलन की ओर जाता है, जिसके लिए आप एक मानचित्र में योग को कुंजी और मूल्य के रूप में संग्रहीत कर सकते हैं, विभिन्न जोड़े की एक सरणी जो योग के योग के लिए है ताकि हर बार जब आप बाइनरी खोज को फिर से संचालित करना चाहते हैं, तो पहले आप जांच लें यदि उस मानचित्र में योग पहले से मौजूद है और यदि ऐसा होता है तो आप मानचित्र में उस योग के सूचकांक में पाए जाने वाले प्रत्येक जोड़े के संयोजन को ऋणात्मक योग के साथ जोड़ सकते हैं।

1
dgmz 7 जून 2020, 04:15
अच्छी सलाह, धन्यवाद - ऐसा लगता है कि मैं जिस अनुकूलन की तलाश कर रहा हूं वह द्विआधारी खोज है, मैं इसे आज़मा दूंगा।
 – 
AnchovyLegend
7 जून 2020, 03:54
यदि यह उत्तर आपकी आवश्यकताओं के अनुरूप है तो आप इसे उत्तर के रूप में भी चिह्नित कर सकते हैं;) यह अहंकार के लिए अच्छा है: डी
 – 
dgmz
7 जून 2020, 05:20
सलाह के लिए धन्यवाद, क्या आप अपने द्विआधारी खोज दृष्टिकोण के लिए कुछ कोड पोस्ट कर सकते हैं?
 – 
AnchovyLegend
7 जून 2020, 17:16
वास्तव में मुझे लगता है कि सेल्फी का समाधान और भी तेज होगा क्योंकि आपकी स्थिति के अनुरूप कुछ बाइनरी सर्च कोड की अभी भी आवश्यकता नहीं है। मैं बस उसका संस्करण लूंगा। और आप वास्तव में उसके उत्तर को मान्य कर सकते हैं क्योंकि यह सबसे अच्छा है।
 – 
dgmz
7 जून 2020, 17:51
var threeSum = function(unsortedNums) {
    const nums = unsortedNums.sort();

    if(nums.length && (nums[0] > 0 || nums[nums.length-1] < 0)) {
        return [];
    }

    const result = new Map();

    for(let i=0; i < nums.length; i++) {
        for(let z=i+1; z < nums.length; z++) {
            for(let q=z+1; q < nums.length; q++) {
                if(nums[i]+nums[z]+nums[q] === 0) {
                    const toAdd = [nums[i], nums[z], nums[q]];            
                    const toAddStr = toAdd.join(',');

                    if(!result.has(toAddStr)) {
                        result.set(toAddStr, toAdd);
                    }
                }
            }
        }
    }

    return Array.from(result.values());
};
0
AnchovyLegend 7 जून 2020, 03:30

OP का समाधान बिना किसी अतिरिक्त संग्रहण के O(N³) समय में चलता है।

लापता तत्व को खोजने के लिए क्लासिक "हैश टेबल का उपयोग करें" समाधान O(N) स्टोरेज के साथ इसे O(N²) समय तक ला सकता है।

समाधान में किसी वस्तु का उपयोग करके एक संख्या मानचित्र बनाना शामिल है। (आप मानचित्र ऑब्जेक्ट का भी उपयोग कर सकते हैं, लेकिन तब आप ++ और -- ऑपरेटरों के साथ उतने अभिव्यंजक नहीं हो सकते)। फिर सभी जोड़ियों का मूल्यांकन करने के लिए बस एक साधारण लूप और इनर लूप। प्रत्येक जोड़े के लिए, पता करें कि क्या उन युग्मों का ऋणात्मक योग मानचित्र में है।

function threeSum(nums) {

    var nummap = {};    // map a value to the number of ocurrances in nums
    var solutions = new Set(); // map of solutions as strings

    // map each value in nums into the number map
    nums.forEach((val) => {
        var k = nummap[val] ? nummap[val] : 0; // k is the number of times val appears in nummap
        nummap[val] = k+1; // increment by 1 and update
    });

    // for each pair of numbers, see if we can find a solution the number map
    for (let i = 0; i < nums.length; i++) {

        var ival = nums[i];
        nummap[ival]--;

        for (let j = i+1; j < nums.length; j++) {
            var jval = nums[j];
            nummap[jval]--;

            var target = -(ival + jval); // this could compute "-0", but it works itself out since 0==-0 and toString will strip the negative off

            // if target is in the number map, we have a solution
            if (nummap[target]) {

                // sort this three sum solution and insert into map of available solutions
                // we do this to filter out duplicate solutions
                var tmp = [];
                tmp[0] = ival;
                tmp[1] = jval;
                tmp[2] = target;

                tmp.sort();
                solutions.add(tmp.toString());
            }

            nummap[jval]++; // restore original instance count in nummap
        }
        nummap[ival]--;
    }

    for (s of solutions.keys()) {
        console.log(s);
    }

}

threeSum([9,8,7,-15, -9,0]);
1
selbie 7 जून 2020, 05:05
वास्तव में यह समाधान मेरे द्वारा प्रस्तावित समाधान में द्विआधारी खोज बिट से बचता है जो कुछ एल्गोरिथम थकाऊपन को बचाता है।
 – 
dgmz
7 जून 2020, 05:37