จัดเรียงอาร์เรย์ให้ arr[i] = i ใน C++

เราได้รับอาร์เรย์จำนวนเต็มบวกขนาดใดก็ตาม ซึ่งค่าของสมาชิกในอาร์เรย์จะมากกว่า 0 แต่น้อยกว่าขนาดของอาร์เรย์ งานคือจัดเรียงอาร์เรย์ใหม่เพื่อให้ arr[i] = i หากค่า i มีอยู่ในอาร์เรย์ มิฉะนั้นให้กำหนดค่า arr[i] เป็น -1 และแสดงผลลัพธ์สุดท้าย

ตัวอย่างการทำงาน (Input/Output)

ตัวอย่างที่ 1

Input: int arr[] = {0, 8, 1, 5, 4, 3, 2, 9}

Output: Rearrangement of an array such that arr[i] = i is: 0 1 2 3 4 5 -1 -1

คำอธิบาย: อาร์เรย์ขนาด 8 มีค่าทุกตัวน้อยกว่า 8 หลังจัดเรียงใหม่:

arr[0] = 0 (มีในอาร์เรย์)
arr[1] = 1 (มีในอาร์เรย์)
arr[2] = 2 (มีในอาร์เรย์)
arr[3] = 3 (มีในอาร์เรย์)
arr[4] = 4 (มีในอาร์เรย์)
arr[5] = 5 (มีในอาร์เรย์)
arr[6] = -1 (ไม่มีในอาร์เรย์)
arr[7] = -1 (ไม่มีในอาร์เรย์)

ตัวอย่างที่ 2

Input: int arr[] = {1, 2, 6, 9, 10}

Output: Rearrangement of an array such that arr[i] = i is: -1 1 2 -1 -1

คำอธิบาย: อาร์เรย์ขนาด 5 มีค่าทุกตัวน้อยกว่า 5 หลังจัดเรียงใหม่:

arr[0] = -1 (ไม่มีในอาร์เรย์)
arr[1] = 1 (มีในอาร์เรย์)
arr[2] = 2 (มีในอาร์เรย์)
arr[3] = -1 (ไม่มีในอาร์เรย์)
arr[4] = -1 (ไม่มีในอาร์เรย์)

อัลกอริทึมที่ใช้

• รับอาร์เรย์จำนวนเต็มและคำนวณขนาด

พิมพ์อาร์เรย์ก่อนจัดเรียง และเรียกฟังก์ชัน Rearranging(arr, size)

• ภายในฟังก์ชัน Rearranging(arr, size):
  • ประกาศตัวแปร ptr ชนิดจำนวนเต็ม
  • วนลูป for จาก i = 0 ถึง size-1 ภายในวนลูป for อีกชั้นจาก j = 0 ถึง size-1
  • ตรวจสอบ if (arr[j] == i) ให้สลับค่า arr[j] กับ arr[i] โดยใช้ ptr เป็นตัวช่วย แล้ว break
  • วนลูป for จาก i = 0 ถึง size-1 ตรวจสอบ if (arr[i] != i) ให้กำหนด arr[i] = -1
• พิมพ์อาร์เรย์หลังจัดเรียงใหม่

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void Rearranging(int arr[], int size) {
    int ptr;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (arr[j] == i) {
                ptr = arr[j];
                arr[j] = arr[i];
                arr[i] = ptr;
                break;
            }
        }
    }
    for (int i = 0; i < size; i++) {
        if (arr[i] != i) {
            arr[i] = -1;
        }
    }
}

int main() {
    int arr[] = {0, 8, 1, 5, 4, 3, 2, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    // เรียกฟังก์ชันจัดเรียงอาร์เรย์ให้ arr[i] = i
    Rearranging(arr, size);
    // แสดงผลอาร์เรย์
    cout << "Rearrangement of an array such that arr[i] = i is: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

ผลลัพธ์

การรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Rearrangement of an array such that arr[i] = i is: 0 1 2 3 4 5 -1 -1