ຈັດແຈງ Array ສິ່ງທີ່ມາຮອດ [i] ແມ່ນເທົ່າກັບ i


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Accenture Adobe Amazon ສະ ເໜ່ ສີ່ພັນ Zoho
Array Hash

“ ຈັດແຈງອາຄານເຊັ່ນວ່າມາຮອດ [i] = i” ບັນຫາລະບຸວ່າທ່ານໄດ້ຮັບເລກເຕັມນັບຕັ້ງແຕ່ 0 ເຖິງ n-1. ເນື່ອງຈາກວ່າທຸກໆອົງປະກອບອາດຈະບໍ່ມີຢູ່ໃນອາເລ, ຫຼັງຈາກນັ້ນ, ຢູ່ບ່ອນທີ່ພວກມັນ -1 ແມ່ນຢູ່. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຮຽກຮ້ອງໃຫ້ຈັດແຈງການຈັດລຽງ ໃໝ່ ດັ່ງກ່າວຖ້າ ຈຳ ນວນລະຫວ່າງຊ່ວງທີ່ບໍ່ມີຢູ່ໃນອາເລຫຼັງຈາກນັ້ນໃຫ້ ໝາຍ ວ່າມັນເປັນ -1 ແລະຈັດລຽງອົງປະກອບຕ່າງໆທີ່ມາຮອດ [i] = i.

ຍົກຕົວຢ່າງ

arr[]={9,4,-1,-1,2,7,8,1,5,-1}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

ຄໍາອະທິບາຍ: ນັບຕັ້ງແຕ່ມີ ອົງປະກອບແມ່ນບໍ່ມີຢູ່ໃນຂອບເຂດ ຫຼັງຈາກນັ້ນ, ມັນຖືກທົດແທນດ້ວຍ -1 ແລະວ່າດັດຊະນີຂບວນໄດ້ຖືກທົດແທນດ້ວຍຕົວມັນເອງ.

ສູດການຄິດໄລ່ ສຳ ລັບການຄົ້ນຫາແຖວ ໃໝ່ ເຊັ່ນວ່າການເຂົ້າມາຂອງຂ້ອຍແມ່ນເທົ່າກັບ i

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

ຄໍາອະທິບາຍ

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

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

ພວກເຮົາພຽງແຕ່ຕ້ອງການແລກປ່ຽນຄ່າທີ່ມີຄ່າຫລາຍກວ່າ 0 ເທົ່ານັ້ນແລະບໍ່ເທົ່າກັບ i. ພ້ອມກັນນີ້, ພວກເຮົາ ກຳ ລັງແລກປ່ຽນກັບແຖວທີ່ມີວົງດຽວ, ໃນຂອບເຂດ, ນັ້ນແມ່ນເຫດຜົນທີ່ພວກເຮົາໄດ້ ນຳ ເອົາຄ່າຂອງຕົວ [al] ມາແລກປ່ຽນ. ແລະສຸດທ້າຍພິມຄຸນຄ່າຂອງອາເລ.

ຈັດແຈງແຖວຕ່າງໆທີ່ມາຮອດ [i] = i

ການປະຕິບັດ

C ++ program to Rearrange an Array ສິ່ງທີ່ມາຮອດ [i] ແມ່ນເທົ່າກັບ i

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}
-1 1 2 -1 4 5 -1 7 8 9

ໂປແກຼມ Java ຫາ Rearrange a Array ດັ່ງກ່າວທີ່ມາຮອດ [i] ແມ່ນເທົ່າກັບ i

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

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

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

ເນື່ອງຈາກວ່າພວກເຮົາຫາກໍ່ຜ່ານແຖວ, ພວກເຮົາໄດ້ບັນລຸຄວາມສັບສົນໃນໄລຍະເວລາ. ໂອ (N) ບ່ອນທີ່ "N" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນແຖວ ສຳ ລັບ“ ຈັດ ລຳ ດັບອາຄານເຊັ່ນທີ່ມາຮອດ [i] = i”.

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

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