मैं एक ऐसा फ़ंक्शन बनाना चाहता हूं जो किसी संख्या में लगातार अंक होने या न होने पर सत्य लौटाए,

उदाहरण:

  • यदि इनपुट 11 है, तो यह सच हो जाएगा
  • यदि इनपुट 21 है तो यह झूठी वापसी करेगा
  • यदि इनपुट 323 है तो यह असत्य लौटेगा क्योंकि भले ही हमारे पास 3 बार-बार हों, वे लगातार नहीं हैं

मेरा समाधान अभी संख्या को एक सरणी में बदलना है और नंबर एक के माध्यम से लूप करना है, यदि अगली संख्या वर्तमान संख्या के बराबर है तो हम केवल सत्य लौटते हैं। लेकिन इसमें ओ (एन) का जटिलता समय है और मैं सोच रहा था कि कोई बेहतर समाधान के साथ आ सकता है या नहीं।

शुक्रिया

2
Pety Ialimijoro Rakotoniaina 15 जिंदा 2022, 22:17
1
क्या आप दिखा सकते हैं कि आपने क्या प्रयास किया है? इस उद्देश्य के लिए O(n) से बेहतर कुछ की कल्पना करना कठिन है।
 – 
skara9
15 जिंदा 2022, 22:19
3
पहचान की जांच के लिए आपको स्पष्ट रूप से सभी अंकों की जांच करने की आवश्यकता है, इसलिए आप n = अंकों की संख्या के साथ ओ (एन) से नीचे जाने में सक्षम होने की संभावना नहीं रखते हैं।
 – 
LSerni
15 जिंदा 2022, 22:33
2
आपका ओ (एन) एल्गोरिदम इस समस्या के लिए सबसे अच्छी समय जटिलता है जिसे आप प्राप्त कर सकते हैं। रेगुलर एक्सप्रेशन से जुड़े समाधान सिर्फ लूप को रेगेक्स इंजन को सौंप रहे हैं।
 – 
Bill the Lizard
15 जिंदा 2022, 22:36
@BilltheLizard: 2345674396539588934682364823553 और अधिक जैसे सुपर लंबी संख्याओं के लिए ... मुझे लगता है कि रेगेक्स केवल 10 पुनरावृत्तियों (मेरा उत्तर देखें) करेगा। तो यह तेज होना चाहिए।
 – 
Louys Patrice Bessette
15 जिंदा 2022, 22:44
1
गलत। क्या आपने अपने दावे का समर्थन करने के लिए RegEx इंजन के कार्यान्वयन की जाँच की है? या कोई प्रदर्शन तुलना चलाएँ? यदि नहीं, तो अनुमान लगाना बंद कर दें।
 – 
Jonas Wilms
15 जिंदा 2022, 23:13

6 जवाब

यकीनन एक बेहतर समाधान है जहाँ आपको संख्या को एक स्ट्रिंग या संख्याओं/वर्णों की सरणी में बदलने की आवश्यकता नहीं है। यह निम्नानुसार काम करता है:

  1. एक वैरिएबल curr से -1 में इनिशियलाइज़ करें।
  2. एक लूप while num > 0 चलाएँ और निम्न कार्य करें:
  • next_curr = num % 10
  • if next_curr == curr: return true
  • curr = next_curr
  • num = num / 10 (पूर्णांक विभाजन)
  1. यदि लूप पूरा हो जाता है, तो झूठी वापसी करें।

यह एक पास O(log n) समय जटिलता एल्गोरिथ्म है जहां n इनपुट नंबर है। अंतरिक्ष जटिलता O(1) है

ध्यान दें कि जबकि आपका एल्गोरिथ्म भी O(log n) समय जटिलता था, इसने 2 पास किए, और इसमें O(log n) की अंतरिक्ष जटिलता भी थी।

मैंने पिछले कुछ समय से JS नहीं लिखा है, लेकिन यहाँ JS में उपरोक्त एल्गोरिथम का संभावित कार्यान्वयन है:

function sameAdjacentDigits(num) {
    // to deal with negative numbers and
    // avoid potential problems when using Math.floor later
    num = Math.abs(num)
    let curr = -1
    while (num > 0) {
        const nextCurr = num % 10
        if (nextCurr == curr) return true
        curr = nextCurr
        num = Math.floor(num / 10)
    }
    return false
}
4
user1984 15 जिंदा 2022, 22:54
1
ओपी एक संख्या को एक सरणी में परिवर्तित करता है, इसलिए प्रारंभिक इनपुट एक संख्या है, न कि एक स्ट्रिंग।
 – 
mister wtf
15 जिंदा 2022, 23:09
1
मुझे डर है कि तुम बहुत दूर जा रहे हो :-|
 – 
mister wtf
15 जिंदा 2022, 23:10
3
यदि आप इनपुट के अंकों पर लूप कर रहे हैं, तो n इनपुट की लंबाई होनी चाहिए, न कि इसका मान। यह एल्गोरिथम भी ओ (एन) है।
 – 
Bill the Lizard
15 जिंदा 2022, 23:16
1
हाँ, मैं इसके बारे में सोच रहा था, "n इनपुट नंबर है" मुझे अजीब लगता है।
 – 
mister wtf
15 जिंदा 2022, 23:17
1
जबकि मैं सहमत हूं कि प्रस्तुत एल्गोरिदम बेहतर है, मैं ओ (लॉग एन) चीज़ से असहमत हूं। उस तर्क के साथ, आप प्रत्येक एल्गोरिदम को केवल n का अर्थ बदलकर "सुधार" कर सकते हैं। परंपरागत रूप से यह एक ट्यूरिंग मशीन के बैंड की लंबाई को संदर्भित करता है, और इसे उसी तरह इस्तेमाल किया जाना चाहिए।
 – 
Jonas Wilms
15 जिंदा 2022, 23:19

इसे निष्पादित करने का सबसे आसान तरीका रेगेक्स का उपयोग करना है। सुनिश्चित नहीं है कि एल्गोरिदम की प्रभावशीलता क्या होगी, लेकिन समाधान हो सकता है

/(\d)\1/

1
mäksä 15 जिंदा 2022, 22:43

कुछ रेगेक्स का प्रयोग करें, और फिर जांचें कि मिलानकर्ता के माध्यम से क्या मिला था

numbers_match = /(00|11|22|33|44|55|66|77|88|99)/;
numbers_match.match("11")

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/match

0
Tschallacka 15 जिंदा 2022, 22:26
धन्यवाद लेकिन समय जटिलता के बारे में, क्या आपको नहीं लगता कि यह अभी भी ओ (एन) है?
 – 
Pety Ialimijoro Rakotoniaina
15 जिंदा 2022, 22:41

@ Tschallacka के उत्तर से प्रेरित:

let numbers = [11,21,323];

let result = numbers.map(n=>{
  let test = n.toString().match(/(00|11|22|33|44|55|66|77|88|99)/);
  return test != null;
})

console.log(result);
0
Louys Patrice Bessette 15 जिंदा 2022, 22:34
आपकी मदद के लिए धन्यवाद, लेकिन मुझे रेगेक्स की समय जटिलता के बारे में निश्चित नहीं है, मुझे लगता है कि मैच को सही खोजने के लिए अभी भी सभी तारों को लूप करना है?
 – 
Pety Ialimijoro Rakotoniaina
15 जिंदा 2022, 22:47
मुझे यकीन नहीं है कि रेगेक्स आंतरिक रूप से लूप का प्रदर्शन कैसे कर रहा है ... लेकिन मुझे लगता है कि इसे केवल 10 बार (दस संभावनाओं के लिए) लूप करना चाहिए। तो सुपर लंबी संख्याओं पर, यह सभी अंकों को पुनरावृत्त करने से तेज़ होना चाहिए... फिर से, मैं इसके बारे में अनिश्चित हूं।
 – 
Louys Patrice Bessette
15 जिंदा 2022, 22:50
मैंने CodePen पर निष्पादन समय मापने का प्रयास किया और... यह BigInt के लिए भी मिलीसेकंड से भी कम दिखाई देता है।
 – 
Louys Patrice Bessette
15 जिंदा 2022, 23:10

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

function hasConsecutive(input) {
    const str = String(input);
    let last;
  
    for (let i = 0; i < str.length; i += 2) {
        if (str[i] === last) return true;
        if (str[i] === str[i + 1]) return true;
        last = str[i + 1];
    }
    
    return false;
}

console.log(hasConsecutive(123455678));
-1
Keytel 15 जिंदा 2022, 22:35
    function has_consecutive_digits(num) {
    for (let index = 0; num>0; index++) {
        var lastdigit = num%10
        var newnum = intval(num/10)
        var beforelastdigit = newnum%10
        if(beforelastdigit == lastdigit){
            return true;
        }
        num = intval(num/10)
    }
}
-1
Amir Abedini 15 जिंदा 2022, 22:42