په ترتیب کې ورته ورته ټکي حذف کړئ


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي حقیقت
پیشه ترتیب کول د دلۍ تار

ستونزه بیان

ستونزه "په ورته ترتیب ورته ورته ټکي حذف کړئ" وايي چې تاسو ته a درکړل شوي لست د ځړونه. که دلته دوه ورته ټکي په پرله پسې ډول شتون ولري ، نو دا دواړه حذف کړئ. په لیست کې د پاتې ټولو ټکو / تارونو ټول شمیره د ورته ټولو جوړه ایستلو له مینځه وړلو وروسته چاپ کړئ.

په ترتیب کې ورته ورته ټکي حذف کړئ

بېلګه

s[ ] = {ab, aa, aa, bcd, ab}
3
s[ ] = {cpp, cpp, java}
1

د دلۍ کارول

الګوریتم

  1. لیست پیل کړئ n ځړونه.
  2. جوړ کړئ ډک د معلوماتو جوړښت.
  3. د لیست له اندازې څخه تر اندازې پورې - 0.
    1. وګوره چې ګ theه تشه ده د بیلګې په توګه د دلۍ اندازه 0 ده
      1. په ستن کې لیست کې اوسني شاخص کې ټکی فشار کړئ / ټک کړئ.
    2. نور د تار تغیر رامینځته کړئ او تار د دې وسیلو په پورتنۍ برخه کې ذخیره کړئ.
      1. په لیست کې اوسني شاخص کې د تار تغیر سره پرتله کړئ ، که دواړه تارونه یو شان وي.
        1. تار د زنګ له پورتنۍ برخې څخه لرې کړئ.
      2. نور که تارونه مختلف دي.
        1. تار په اوسني لړلیک سوري ته وخورئ.
  4. د دلۍ اندازه بیرته راستانه کړئ.

کوډ

په ترتیب کې ورته ورته ټکي حذف کولو لپاره C ++ برنامه

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

د جاوا برنامې په ترتیب کې ورته ورته ټکي حذف کول

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) چیرې چې n په لیست کې د تارونو شمیر دی. لکه څنګه چې موږ یوازې د تارونو څخه تیریږو ، د وخت پیچلتیا په ساده ډول O (n) ده ، کوم چې الګوریتم په خطي وخت کې پرمخ وړي. مګر یو شی چې په یاد ولرئ دا دی چې تارونه پرتله کیږي او موږ په پام کې لرو چې تارونه یو ثابت دوام لري چې د N څخه کم دی. ځکه چې په بدترین حالت کې د تار پرتله O (اوږدوالي) وخت نیسي.

د ځای پیچلتیا

اې (N) ځکه چې موږ د n تارونو ذخیره کولو لپاره ځای کارولی و. هرکله چې اوسني شاخص کې تار او د سټیک په پورتنۍ برخه کې تار یو شان نه وي. موږ تار په اوسني شاخص کې په زېرمو فشار ورکوو. په بدترین حالت کې ، موږ ممکن پای ته ورسېږو ټول تارونه په کڅوړه کې. دا سناریو د O (n) ځای پیچلتیا پایله ده.

پرته د سټا کارولو پرته

الګوریتم

  1. لیست پیل کړئ n تارونه
  2. د لیست له اندازې څخه تر اندازې پورې - 0.
    1. په لیست کې اوسني شاخص کې ټکی په اوسني شاخص + 1 کې په لیست کې پرتله کړئ.
      1. که دواړه تارونه سره توپیر ولري.
        1. د اوسني شاخص زیاتوالی
      2. نور که دواړه تارونه یو شان وي.
        1. له لیست څخه دواړه تارونه لرې / پاک کړئ.
        2. وګوره که موجوده شاخص د 0 څخه لوی وي
          1. د اوسني شاخص کمول.
        3. د لیست اندازې په توګه د لیست اندازه تازه کړئ - 2.
  3. د لیست کچه ​​راوباسي.

کوډ

په ترتیب کې ورته ورته ټکي حذف کولو لپاره C ++ برنامه

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}
3

د جاوا برنامې په ترتیب کې ورته ورته ټکي حذف کول

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}
3

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n ^ 2) چیرې چې n په لیست کې د تارونو شمیر دی. ځکه چې موږ د ویکټر څخه تارونه لرې کوو. د ویکتور څخه د هر عنصر لرې کول لین وخت نیسي. ځکه چې دا عملیات N وخت ترسره کیدی شي. د وخت پیچلتیا ډیره ده.

د ځای پیچلتیا

O (1) ځکه چې موږ د معلوماتو ذخیره کولو لپاره د منځمهاله معلوماتو جوړښت نه کارولی. یوازینۍ ځای د تارونو ذخیره کولو لپاره اړین و ، کوم چې د آخذې برخه ده او د الګوریتم لپاره د ځای پیچلتیا محاسبه کولو کې به پام ونشي. مګر برنامه په مجموع کې لاهم د O (N) ځای نیسي.