ตรวจสอบว่า Array เป็นแบบเรียงซ้อนได้หรือไม่  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ แอคโคไลท์ อเมซอน
แถว การเรียงลำดับ กอง

ในการตรวจสอบว่าไฟล์ แถว คือปัญหาการเรียงลำดับสแต็กเราได้กำหนด [] ของขนาด n อาร์เรย์ที่มีองค์ประกอบตั้งแต่ 1 ถึง n ตามลำดับแบบสุ่ม เรียงลำดับอาร์เรย์จากน้อยไปหามากโดยใช้ชั่วคราว กอง ตามการดำเนินการสองอย่างนี้เท่านั้น -

  • ลบองค์ประกอบที่ดัชนีเริ่มต้นในอาร์เรย์และเก็บไว้ในสแต็ก
  • เปิดด้านบนจากสแต็กและต่อท้ายที่ส่วนท้ายของอาร์เรย์อื่น

ตรวจสอบว่าสามารถจัดเรียงอาร์เรย์ที่กำหนดโดยใช้สแต็กได้หรือไม่

ตรวจสอบว่า Array เป็นแบบเรียงซ้อนได้หรือไม่หมุด

ตัวอย่าง  

อินพุต

ก [] = {4, 1, 2, 3}

เอาท์พุต

อาร์เรย์ที่ระบุสามารถจัดเรียงโดยใช้สแต็ก

อินพุต

ก [] = {2, 3, 1}

เอาท์พุต

ไม่สามารถจัดเรียงอาร์เรย์โดยใช้สแต็กได้

ขั้นตอนวิธี  

  1. เริ่มต้นอาร์เรย์ a [] ขนาด n
  2. สร้างสแตกเพื่อเก็บองค์ประกอบเพื่อจัดเรียงอาร์เรย์และตัวแปร end = 0 เพื่อชี้จุดสิ้นสุด
  3. สำรวจจาก 0 ถึง n-1 และตรวจสอบว่าสแต็กว่างหรือไม่ให้ดันค่าของอาร์เรย์ที่ดัชนีปัจจุบันในสแต็ก เก็บด้านบนของสแต็กไว้ในตัวแปรด้านบน ในขณะที่ด้านบนเท่ากับ end + 1 ให้เพิ่มจุดสิ้นสุดและปรากฏด้านบน ตรวจสอบว่าสแต็กว่างเปล่าทำลายลูปหรือไม่ อัปเดตตัวแปรด้านบนเป็นด้านบนปัจจุบันในสแต็ก
  4. หากสแต็กว่างเปล่าให้กดค่าของอาร์เรย์ที่ดัชนีปัจจุบันในสแต็ก
  5. เก็บด้านบนของสแต็กไว้ในตัวแปรด้านบน ตรวจสอบว่าค่าของอาร์เรย์ที่ดัชนีปัจจุบันน้อยกว่าด้านบนหรือไม่ให้ดันองค์ประกอบอาร์เรย์ในสแต็ก อื่นกลับเท็จ
  6. กลับจริง.
ดูสิ่งนี้ด้วย
ค้นหาความแตกต่างสูงสุดระหว่างองค์ประกอบขนาดเล็กทางซ้ายและขวาที่ใกล้ที่สุด

โปรแกรม C ++ สำหรับตรวจสอบว่า Array เป็นแบบเรียงซ้อนได้หรือไม่  

#include <bits/stdc++.h> 
using namespace std; 
  
bool check(int a[], int n){ 
    
    stack<int> S; 
  
    int end = 0; 
  
    for(int i = 0; i < n; i++){ 
        
        if(!S.empty()){ 
            
            int top = S.top(); 
  
            while(top == end + 1){ 
                end = end + 1; 
  
                S.pop(); 
  
                if(S.empty()){ 
                    break; 
                } 
  
                top = S.top(); 
            } 
  
            if(S.empty()) { 
                S.push(a[i]); 
            } 
            
            else{ 
                top = S.top(); 
  
                if(a[i] < top){ 
                    S.push(a[i]); 
                } 
                else{ 
                    return false; 
                } 
            } 
        } 
        else{ 
            S.push(a[i]); 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    int a[] = {4, 1, 2, 3}; 
    int n = sizeof(a) / sizeof(a[0]);
    
    check(a, n)? cout<<"Given array can be sorted using stack.": cout<<"Given array can not be sorted using stack.";    
    
    return 0; 
}
Given array can be sorted using stack.

โปรแกรม Java สำหรับตรวจสอบว่า Array เป็น Stack Sortable หรือไม่  

import java.util.Stack; 
  
class soryArray{ 
  
    static boolean check(int a[], int n){ 
        
        Stack<Integer> S = new Stack<Integer>(); 
  
        int end = 0; 
  
        for(int i = 0; i < n; i++) { 
            if(!S.empty()){ 
                int top = S.peek(); 
  
                while(top == end + 1){ 
                    end = end + 1; 
  
                    S.pop(); 
  
                    if(S.empty()){ 
                        break; 
                    } 
  
                    top = S.peek(); 
                } 
  
                if (S.empty()) { 
                    S.push(a[i]); 
                } 
                else{ 
                    top = S.peek(); 
  
                    if(a[i] < top) { 
                        S.push(a[i]); 
                    } 
                    else{ 
                        return false; 
                    } 
                } 
            } 
            else{ 
                S.push(a[i]); 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args) { 
  
        int a[] = {4, 1, 2, 3}; 
        int n = a.length; 
  
        if(check(a, n)){ 
            System.out.println("Given array can be sorted using stack."); 
        } 
        else{ 
            System.out.println("Given array can not be sorted using stack."); 
        } 
  
    } 
}
Given array can be sorted using stack.

การวิเคราะห์ความซับซ้อนเพื่อตรวจสอบว่าอาร์เรย์เป็นแบบเรียงซ้อนได้หรือไม่  

ความซับซ้อนของเวลา: O (n) โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์

ความซับซ้อนของอวกาศ: O (n) เนื่องจากเราใช้พื้นที่ในการจัดเก็บองค์ประกอบ n

อ้างอิง