การกลับลำดับของคำในอาเรย์ตัวอักษรอย่างมีประสิทธิภาพ

การกลับลำดับของคำในอาเรย์ตัวอักษรเป็นปัญหาคลาสสิคที่ตรวจสอบความเข้าใจของคุณเกี่ยวกับอัลกอริธึมและการจัดการสตริง ไม่ว่าจะเป็นการเตรียมตัวสำหรับสัมภาษณ์หรือลับคมทักษะการเขียนโปรแกรมของคุณ การเชี่ยวชาญในความท้าทายนี้เป็นสิ่งที่คุ้มค่า ในโพสต์นี้ เราจะสำรวจปัญหาในรายละเอียดและแบ่งการแก้ปัญหาที่มีประสิทธิภาพใน C/C++

ปัญหา

ให้พิจารณาอาเรย์ของตัวอักษรที่สร้างเป็นประโยค เรามุ่งหมายที่จะ กลับลำดับของคำ โดยไม่เปลี่ยนแปลงตัวอักษรในแต่ละคำ ตัวอย่างเช่น ถ้าคุณป้อน:

"this is a string"

ผลลัพธ์ควรเป็น:

'string a is this'

ความท้าทายกำหนดว่า การดำเนินการนี้จะต้องทำให้เสร็จใน เวลา O(N) และ พื้นที่ O(1) ซึ่งหมายความว่าคุณไม่สามารถใช้ฟังก์ชันเช่น split() หรือโครงสร้างข้อมูลอื่นๆ เช่น สแตกที่ใช้พื้นที่เพิ่มเติมได้

การวิเคราะห์ปัญหา

เวลาที่ใช้ในการประมวลผล

ความต้องการสำหรับความซับซ้อนเวลา O(N) หมายความว่า อัลกอริธึมจะต้องทำการวนซ้ำแบบเชิงเส้นผ่านข้อมูล ดังนั้นเราควรหลีกเลี่ยงการใช้ลูปที่ซ้อนกันที่เพิ่มความซับซ้อนไปมากขึ้น

พื้นที่ที่ใช้ในการประมวลผล

สำหรับความซับซ้อนพื้นที่ O(1) เราไม่สามารถใช้โครงสร้างข้อมูลเพิ่มเติมเพื่อเก็บข้อมูลได้ ซึ่งหมายความว่าการดำเนินการทั้งหมดจะต้องเกิดขึ้นภายในอาเรย์ที่ใช้เข้ามา

การแก้ปัญหา

เรามาแบ่งการแก้ปัญหาออกเป็นขั้นตอน โดยจะใช้วิธีการวนซ้ำสองครั้งเพื่อแก้ปัญหานี้อย่างมีประสิทธิภาพ

ขั้นตอนที่ 1: การกลับอาเรย์ทั้งหมด

ขั้นตอนแรกคือการกลับอาเรย์ทั้งหมด ซึ่งจะเปลี่ยนสตริงต้นฉบับให้เป็นสตริงที่ตัวอักษรทั้งหมดถูกกลับ ในตัวอย่างของเรา "this is a string" หลังจากกลับจะเป็น:

"gnirts a si siht"

ขั้นตอนที่ 2: การกลับแต่ละคำ

ตอนนี้เราได้กลับอาเรย์ทั้งหมดแล้ว เราต้องกลับแต่ละคำกลับมาที่ลำดับที่ถูกต้อง นี่คือวิธีการที่เราสามารถดำเนินการเหล่านี้ใน C/C++:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // กลับอาเรย์ทั้งหมด
    reverse_string(str, strlen(str));
    int p = 0;
 
    // หาขอบเขตของคำและกลับคำโดยคำ
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // กลับคำที่ระบุ
            p = i + 1;
        }
    }
    // สุดท้ายกลับคำสุดท้าย
    reverse_string(&str[p], l - p);
}

อธิบายโค้ด

1. ฟังก์ชัน Swap: เราใช้ฟังก์ชันช่วย swap เพื่อแลกเปลี่ยนตัวอักษรในอาเรย์
2. ฟังก์ชัน Reverse String: ฟังก์ชันนี้ทำให้ตัวอักษรในสตริงกลับไปโดยใช้ฟังก์ชัน swap
3. ฟังก์ชัน Reverse Words: ฟังก์ชันหลักจะกลับอาเรย์ตัวอักษรทั้งหมดก่อน และจากนั้นทำการวนซ้ำเพื่อต้องกลับแต่ละคำที่จำแนกโดยช่องว่าง คำสุดท้ายจะได้รับการจัดการหลังจากที่ลูปจบลง

การวิเคราะห์ความซับซ้อน

การกลับผ่านอาเรย์ 2 ครั้งทำให้ความซับซ้อนเวลาเป็น O(N):

• การวนรอบครั้งแรก: O(N) สำหรับการกลับทั้งสตริง
• การวนรอบครั้งที่สอง: O(N) สำหรับการกลับแต่ละคำ

ดังนั้น ความซับซ้อนเวลาโดยรวมยังคงเป็น O(N) พื้นที่ที่ใช้คือ O(1) เนื่องจากไม่มีพื้นที่เพิ่มเติมถูกใช้ นอกจากตัวแปรสำหรับการวนซ้ำ

สรุป

การกลับลำดับของคำในอาเรย์ตัวอักษรอย่างมีประสิทธิภาพต้องการการรวมกันของการจัดการสตริงและความเข้าใจในการเข้าถึงแบบดัชนี อัลกอริธึมที่นำเสนอในที่นี้แสดงให้เห็นถึงวิธีการที่ชัดเจนที่ตรงตามข้อกำหนดเวลา O(N) และพื้นที่ O(1) ขณะใช้ C/C++ ฝึกฝนการแก้ปัญหานี้และคุณจะพบว่ามันเป็นเครื่องมือที่ยอดเยี่ยมในการเขียนโปรแกรมของคุณ!