ຈັດແຈງແຖວ ໃໝ່ ທີ່ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ເດລີ ກຸລະກິ ນາກາໂຣ Opera ອິນເຕີເນັດ Times Times Yatra
Array

ຖະແຫຼງການບັນຫາ

ບັນຫາ” ຈັດແຈງແຖວຕ່າງໆທີ່ວ່າ 'ມາຮອດ [ຈ]' ຈະກາຍເປັນ 'ຖ້າ' ມາຮອດ [ຂ້ອຍ] 'ແມ່ນ' ຈ '' ລະບຸວ່າທ່ານມີ "n" ຂະ ໜາດ ຂະ ໜາດ ບັນຈຸຕົວເລກ. ຕົວເລກໃນອາເລແມ່ນຢູ່ໃນລະດັບ 0 ເຖິງ n-1. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຮຽກຮ້ອງໃຫ້ຈັດແຈງການຈັດລຽງ ໃໝ່ ໃນແບບທີ່ອາເລ [i] = j ກາຍເປັນ arr [j] = i.

ຍົກຕົວຢ່າງ

arr[]={1,3,5,2,0,4}
4 0 3 1 5 2

ຄໍາອະທິບາຍ

arr [0] = 1 ຖືກປ່ຽນເປັນ arr [1] = 0

arr [1] = 3 ຖືກປ່ຽນເປັນ arr [3] = 1

arr [2] = 5 ຖືກປ່ຽນເປັນ arr [5] = 2

arr [3] = 2 ຖືກປ່ຽນເປັນ arr [2] = 3

arr [4] = 0 ຖືກປ່ຽນເປັນ arr [0] = 4

arr [5] = 4 ຖືກປ່ຽນເປັນ arr [4] = 5

ສະນັ້ນເມື່ອພິມ⇒

arr [0] ⇒ arr [1] ⇒ arr [2] ⇒ arr [3] ⇒ arr [4] ⇒ arr [5]

4 0 3 1 5 2

ສູດການຄິດໄລ່ກັບ Rearrange ແຖວເຊັ່ນວ່າ 'arr [j]' ຈະກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'

1. Traverse the array from 0 to n-1(inclusively).
    1. Do arr [ arr % n ] + = i * n.
2. Then update the value of arr[ i ] =arr[ i ] / n.
3. Print the array.

ຄໍາອະທິບາຍ

ມອບໃຫ້ array of integers. ຕົວເລກທີ່ມັນຖືຢູ່ໃນລະຫວ່າງ 0 ເຖິງ n - 1. ພວກເຮົາຈະຈັດລຽງ ລຳ ດັບເລກ pf. ເພື່ອໃຫ້ອົງປະກອບໃນແຖວກາຍເປັນດັ່ງກ່າວທີ່ມາຮອດ [j] = ຂ້ອຍຖ້າມັນມາຮອດ [i] = j. ດັ່ງນັ້ນ ໝາຍ ຄວາມວ່າຖ້າພວກເຮົາມີຄ່າບາງຢ່າງຢູ່ ຕຳ ແໜ່ງ ith j, ຫຼັງຈາກນັ້ນປ່ຽນຄ່ານັ້ນໄປທີ່ ຕຳ ແໜ່ງ jth ຂອງອາເລ. ນອກຈາກນີ້, ພວກເຮົາຍັງໄດ້ມອບສ່ວນປະກອບ array ພາຍໃນລະດັບ 0 ເຖິງ n-1. ດັ່ງນັ້ນ ຈຳ ນວນບໍ່ສາມາດເກີນຄວາມຍາວຂອງອາເລ. ດັ່ງນັ້ນມັນສາມາດເປັນປະໂຫຍດເມື່ອພວກເຮົາຂ້າມອາເລ, ພວກເຮົາສາມາດຖືເອົາຕົວເລກຕົວເລກໃດໆເປັນດັດສະນີແລະປະຕິບັດບາງຢ່າງໃນມັນ.

ເພາະວ່າພວກເຮົາ ກຳ ລັງຈະ ດຳ ເນີນການບາງຢ່າງກ່ຽວກັບຂບວນຕົວມັນເອງ. ພວກເຮົາຈະເລືອກເອົາແຕ່ລະອົງປະກອບຂອງອາເລແລະພົບ ໂມດູນ of arr [i]% n, ບ່ອນທີ່ n ແມ່ນຄວາມຍາວຂອງຂບວນ. ຕອນນີ້, ດັ່ງທີ່ພວກເຮົາໄດ້ກ່າວມາກ່ອນ ໜ້າ ນີ້ວ່າຕົວເລກແມ່ນຢູ່ໃນລະດັບ 0 ເຖິງ n-1. ສະນັ້ນເມື່ອພວກເຮົາຊອກຫາຮູບແບບຂອງ ຈຳ ນວນໃດ ໜຶ່ງ ທີ່ມີເລກ n. ມັນຈະບໍ່ເກີນຕົວເລກທີ່ໃຫຍ່ກວ່າດັດຊະນີຂອງຂບວນການ, ເພາະວ່າໂມດູນຂອງ arr [i]% n ຈະຖືກປະຕິບັດເປັນດັດຊະນີຂອງອາເລອີກເທື່ອ ໜຶ່ງ. ແລະຫຼັງຈາກນັ້ນພວກເຮົາເກັບມັນໄວ້ໃນຕົວຄູນ i * n. ປັບປຸງແຕ່ລະຄ່າຂອງ modulo ເປັນດັດສະນີຂອງຂບວນແລະສະຫຼຸບມັນດ້ວຍຕົວມັນເອງ.

ພວກເຮົາພຽງແຕ່ເຮັດສິ່ງນີ້ເພື່ອເກັບແລະປັບປຸງຄຸນຄ່າຕ່າງໆໃນອາເລຖ້າພວກເຮົາຈະໄປເກັບເອົາພວກມັນ. ພວກເຮົາພຽງແຕ່ຕ້ອງແບ່ງພວກມັນ. ເພາະຖ້າທ່ານຄູນເລກທີ່ມີ x ແລະແບ່ງດ້ວຍ x ຕົວເລກກໍ່ຈະກາຍເປັນກາງເຊັ່ນດຽວກັນ. ປັບປຸງ arr [i] ໂດຍແບ່ງປັນການເຂົ້າມາຂອງ [i] ດຽວກັນໂດຍ n ແລະເກັບມັນເພື່ອມາຮອດ [i]. ດ້ວຍວິທີນີ້, ພວກເຮົາຈະໄດ້ຮັບຜົນທີ່ຕ້ອງການ. ນັ້ນແມ່ນວິທີການຈັດແຈງແຖວເຊັ່ນວ່າ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'.

ຈັດແຈງແຖວ ໃໝ່ ທີ່ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'

ລະຫັດ

ລະຫັດ C ++ ເພື່ອ Rearrange ແຖວເຊັ່ນວ່າ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'

#include<iostream>

using namespace std;

void rearrangeIndexValue(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[arr[i] % n] += i * n;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] /= n;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,3,5,2,0,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array after modifying :";
    rearrangeIndexValue(arr,n);
    printArray(arr, n);

    return 0;
}
Array after modifying :4 0 3 1 5 2

ລະຫັດ Java ຫາ Rearrange ແຖວເຊັ່ນວ່າ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'

class rearrangeArray2
{
    public static void rearrangeIndexValue(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[arr[i] % n] += i * n;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] /= n;
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,3,5,2,0,4};
        int n = arr.length;

        rearrangeIndexValue(arr, n);

        System.out.print("Array after modifying : ");
        printArray(arr, n);
    }
}
Array after modifying : 4 0 3 1 5 2

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເຖິງແມ່ນວ່າພວກເຮົາໄດ້ຂ້າມຜ່ານອົງປະກອບຂອງອາເລສອງຄັ້ງ. ສະນັ້ນ, ສິ່ງນີ້ຍັງຖືວ່າເປັນເວລາທີ່ມີຄວາມສັບສົນເປັນເສັ້ນເທົ່ານັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ເກັບຮັກສາສິ່ງໃດທີ່ກ່ຽວຂ້ອງກັບແຕ່ລະອົງປະກອບແລະໄດ້ມີການ ນຳ ໃຊ້ພື້ນທີ່ຄົງທີ່ເທົ່ານັ້ນ. ດັ່ງນັ້ນ, ຄວາມສັບສົນໃນພື້ນທີ່ ສຳ ລັບການຄິດໄລ່ແມ່ນຄົງທີ່.