Sắp xếp lại mảng sao cho arr[i] = i trong C++

Chúng ta được cung cấp một mảng số nguyên dương, giả sử arr[] với kích thước bất kỳ, sao cho các phần tử trong mảng có giá trị lớn hơn 0 nhưng nhỏ hơn kích thước của mảng. Nhiệm vụ là sắp xếp lại mảng theo cách mà nếu arr[i] bằng 'i', nếu 'i' có mặt trong mảng, thì giữ nguyên; ngược lại, gán arr[i] = -1 và in kết quả cuối cùng.

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: int arr[] = {0, 8, 1, 5, 4, 3, 2, 9}

Đầu ra: Mảng sau khi sắp xếp sao cho arr[i] = i: 0 1 2 3 4 5 -1 -1

Giải thích: Mảng nguyên bản có kích thước 8, tất cả phần tử đều nhỏ hơn 8. Sau khi sắp xếp:

arr[0] = 0 (có trong mảng)
arr[1] = 1 (có trong mảng)
arr[2] = 2 (có trong mảng)
arr[3] = 3 (có trong mảng)
arr[4] = 4 (có trong mảng)
arr[5] = 5 (có trong mảng)
arr[6] = -1 (KHÔNG có trong mảng)
arr[7] = -1 (KHÔNG có trong mảng)

Đầu vào: int arr[] = {1, 2, 6, 9, 10}

Đầu ra: Mảng sau khi sắp xếp sao cho arr[i] = i: -1 1 2 -1 -1

Giải thích: Mảng có kích thước 5, các phần tử nhỏ hơn 5. Sau khi sắp xếp:

arr[0] = -1 (KHÔNG có trong mảng)
arr[1] = 1 (có trong mảng)
arr[2] = 2 (có trong mảng)
arr[3] = -1 (KHÔNG có trong mảng)
arr[4] = -1 (KHÔNG có trong mảng)

Phương pháp tiếp cận

• Nhập mảng số nguyên và tính kích thước mảng.
• In mảng trước khi sắp xếp và gọi hàm Rearranging(arr, size).
• Trong hàm Rearranging(arr, size):
  • Khai báo biến tạm ptr.
  • Vòng lặp FOR i từ 0 đến size-1. Bên trong, vòng lặp FOR j từ 0 đến size-1.
  • Nếu arr[j] == i, hoán đổi arr[j] và arr[i] thông qua ptr, sau đó break.
  • Vòng lặp FOR i từ 0 đến size-1: nếu arr[i] != i thì gán arr[i] = -1.
• In mảng sau khi sắp xếp lại.

Ví dụ mã 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]);
    // Gọi hàm sắp xếp mảng sao cho arr[i] = i
    Rearranging(arr, size);
    // In mảng kết quả
    cout << "Rearrangement of an array such that arr[i] = i is: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Đầu ra chương trình

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