Հակադարձեք մի կույտ ՝ առանց ավելորդ տեղ օգտագործելու O (n) - ում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Փաստեր Infosys MAQ
Կապված ցուցակ Գրապահոց

Խնդիրի հայտարարություն

«Դիրը հետ շրջել առանց O (n) - ի մեջ լրացուցիչ տարածք օգտագործելու» խնդրի մեջ նշվում է, որ ձեզ տրված է a բուրգ տվյալների կառուցվածքը: Հակադարձեք տրված բուրգը ՝ առանց լրացուցիչ O (n) տարածություն օգտագործելու:

Հակադարձեք մի կույտ ՝ առանց ավելորդ տեղ օգտագործելու O (n) - ում

Օրինակ

5 4 3 2 1
1 2 3 4 5
80 60 10 20
20 10 60 80

Stack- ը շրջելու ալգորիթմ `առանց O (n) - ի մեջ լրացուցիչ տարածություն օգտագործելու

  1. Ստեղծեք ամբողջական փոփոխական և հաջորդ ցուցիչ պարունակող դասի հանգույց: Ստեղծեք դասի կոնստրուկտոր, որն ընդունում է an ամբողջ թիվ որպես պարամետր: Պարամետրի արժեքը նշանակեք ամբողջ փոփոխականին և հաջորդ ցուցիչը դրեք կոնստրուկտորի մեջ որպես զրոյական:
  2. Դրանից հետո ստեղծեք դաս բուրգ և նախանշեք դրա վրա տիպի հանգույցի ցուցիչի վերևը:
  3. Ստեղծեք գործառույթի հրում (), որն ամբողջ թիվն ընդունում է որպես պարամետր: Ստուգեք, արդյոք վերը հավասար է զրոյի, ստեղծեք նոր հանգույց տրված ամբողջ թվով որպես տվյալներ և պահեք նոր հանգույցը վերևում և վերադարձեք:
  4. Այլապես ստեղծեք նոր հանգույց s տրված ամբողջ թվով որպես տվյալներ: S- ի հաջորդ տարբերակը թարմացնել որպես վերև և վերև հավասար է s- ի:
  5. Նմանապես, ստեղծեք pop () գործառույթ: Ստեղծեք նոր հանգույց և պահեք վերևը դրա մեջ: Վերևը թարմացրեք վերևի հաջորդ մասից և վերադարձեք նոր հանգույցը:
  6. Դրանից հետո ստեղծեք reverse () ֆունկցիան: Ստեղծեք համապատասխանաբար նախորդ, ընթացիկ և հաջորդող երեք հանգույց: Թարմացրեք ընթացիկ և նախորդ հանգույցը որպես վերին հանգույց:
  7. Ընթացիկ հանգույցը թարմացրեք որպես ընթացիկ հանգույցի հաջորդ, իսկ նախորդ նախորդ հանգույցը ՝ որպես null:
  8. Չնայած ընթացիկ հանգույցը զրոյական չէ, թարմացրեք հաջորդ հանգույցը որպես ընթացիկ հանգույցի հաջորդը, ընթացիկ հանգույցին հաջորդող ՝ որպես նախադաշտի հանգույց, նախորդ հանգույցը ՝ որպես ընթացիկ հանգույց և ընթացիկ հանգույց ՝ որպես հաջորդ հանգույց:
  9. Թարմացրեք վերին հանգույցը որպես նախորդ հանգույց:
  10. Վերջապես ստեղծեք ֆունկցիայի ցուցադրություն () ՝ հակառակ երեսը ցուցադրելու համար: Ստեղծեք նոր հանգույց և պահեք վերևը դրա մեջ: Չնայած s- ն հավասար չէ null- ի, տպեք s- ի տվյալները և s- ը թարմացրեք s- ի հաջորդ մասի համաձայն:

Կոդ

C ++ ծրագիր ՝ հետ փոխել բուրգը ՝ առանց O (n) - ի մեջ լրացուցիչ տարածություն օգտագործելու

#include<bits/stdc++.h> 
using namespace std; 
  
class Node { 
    public: 
        int data; 
        Node *next; 
          
        Node(int data){ 
            this->data = data; 
            this->next = NULL; 
        } 
}; 
  
class Stack{ 
      
    Node *top; 
      
    public: 
      
        void push(int data){ 
            if (top == NULL) { 
                top = new Node(data); 
                return; 
            } 
            Node *s = new Node(data); 
            s->next = top; 
            top = s; 
        } 
          
        Node* pop(){ 
            Node *s = top; 
            top = top->next; 
            return s; 
        } 
      
        void display(){ 
            Node *s = top; 
            while (s != NULL) { 
                cout << s->data << " "; 
                s = s->next; 
            } 
            cout << endl; 
        } 
      
        void reverse(){ 
            Node *prev, *cur, *succ; 
            cur = prev = top; 
            cur = cur->next; 
            prev->next = NULL; 
            while (cur != NULL) { 
                succ = cur->next; 
                cur->next = prev; 
                prev = cur; 
                cur = succ; 
            } 
            top = prev; 
        } 
}; 
  
int main(){ 
    Stack *s = new Stack(); 
    
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4);
    s->push(5);
    
    s->reverse(); 
  
    s->display(); 
      
    return 0; 
}
1 2 3 4 5

Java ծրագիր `բեռնափոխելու համար առանց O (n) - ի մեջ լրացուցիչ տարածություն օգտագործելու

class Node{ 
    int data; 
    Node next; 
    
    public Node(int data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack{ 
    Node top; 
  
    public void push(int data){ 
        if (this.top == null){ 
            top = new Node(data); 
            return; 
        } 
        
        Node s = new Node(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    
    public Node pop(){ 
        Node s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    public void display(){ 
        Node s = this.top; 
        
        while (s != null){ 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        
    } 
  
    public void reverse(){
        
        Node prev, cur, succ; 
        
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
        
        while(cur != null){ 
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        
        this.top = prev; 
    } 
} 
  
class reverseStack{ 
    
    public static void main(String[] args){ 
        
        Stack s = new Stack(); 
        
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4);
        s.push(5);
        
        s.reverse(); 
  
        s.display(); 
    } 
}
1 2 3 4 5

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ n- ը տվյալների կառուցվածքի բուրգի տարրերի քանակն է: Քանի որ մենք օգտագործել ենք մեկ օղակ ՝ բուրգը տարրերի վրայով անցնելու համար: Timeամանակի բարդությունը գծային է:

Տիեզերական բարդություն

Ո (1) քանի որ մենք անընդհատ լրացուցիչ տարածք ենք օգտագործում: Քանի որ մուտքագրումը պահելու համար վերցված տարածությունը չի հաշվարկվի ալգորիթմի համար: Այսպիսով, տարածության բարդությունը կայուն է: Բայց ծրագիրը, որպես ամբողջություն, պահանջում է գծային տիեզերական բարդություն: