ສຽບເລກເຕັມ 2n ເປັນ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe DE Shaw Expedia ສະ ເໜ່ ແທ້ຈິງແລ້ວ PayU
Array ແບ່ງແລະເອົາຊະນະ Recursion

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

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ array of integers. ປັນຫາ“ ຕົວເລກທີ່ສົມບູນ 2n ເປັນ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ໃຊ້ພື້ນທີ່ພິເສດ” ຂໍໃຫ້ປິດຕົວເລກທັງ ໝົດ ໃນແຖວເຊັ່ນວ່າຕົວເລກທີ່ຄ້າຍຄື (x0, x1, x2, x3, y0, y1, y2, y3) ຈະຖືກສັບປ່ຽນເຊັ່ນ x0, y0, x1, y1, x2, y2, x3, y3 ແລະອື່ນໆໃນລັກສະນະນີ້.

ຍົກຕົວຢ່າງ

arr[]={1, 3, 5, 7, 2, 4, 6, 8}
1, 2, 3, 4, 5, 6, 7, 8

ຄໍາອະທິບາຍ

ຖ້າພວກເຮົາສົມທຽບຈາກສາມຕົວເລກ ທຳ ອິດຈະເປັນຄື x0, x1, x2 ແລະສາມຕົວເລກຕໍ່ໄປຈະເປັນຄື y0, y1, y2, ແລະມັນຈະຈັດເປັນ x0, y0, x1, y1, x2, y2

ສຽບເລກເຕັມ 2n ເປັນ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມ

ສູດການຄິດໄລ່ເພື່ອແຊ່ຕົວເລກ 2n ເປັນ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ພິເສດ

1. Find out the middle index of the array.
2. While middleIndex greater than 0, set count and swappingIndex to middleIndex.
  1. While the count is greater than 0, do the following steps.
    1. Swap the values at swappingIndex and swappingIndex +1(value next to swappingIndex).
    2. Increase the value of swapping index by 1.
  2. Decrease the value of middleIndex by 1.
3. Print the array.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ມອບ array of ເລກເຕັມ.  ຫຼັງຈາກນັ້ນ, ພວກເຮົາຖືກຮ້ອງຂໍໃຫ້ສັບປ່ຽນຄຸນຄ່າທັງ ໝົດ ໃນແບບ, ໂດຍສະເພາະ. ພວກເຮົາຈະໄດ້ຮັບການຂ້າມຜ່ານພຽງແຕ່ເຄິ່ງ ໜຶ່ງ ຂອງຂບວນ. ແລະແລກປ່ຽນຄຸນຄ່າທັງ ໝົດ ທີ່ມາຕາມລະບົບ. ຫນ້າທໍາອິດ, ພວກເຮົາກໍາລັງຈະກວດເບິ່ງວ່າອາເລບໍ່ຄວນຈະຖືກ null. Ans ຍັງ, ຄວາມຍາວຂອງຂບວນການຄວນຈະເປັນແມ້ກະທັ້ງ. ນັ້ນແມ່ນເຫດຜົນທີ່ພວກເຮົາກວດເບິ່ງສະພາບການທີ່ຈັດລວງຍາວບໍ່ຄວນເປັນເລື່ອງແປກ. ຖ້າມີເງື່ອນໄຂໃດ ໜຶ່ງ ທີ່ກ່າວມາຂ້າງເທິງນັ້ນແມ່ນບໍ່ຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນມັນຈະບໍ່ຜະລິດຜົນອອກມາ.

ພວກເຮົາຈະຊອກຫາດັດສະນີກາງຂອງອາເລແລະຫຼັງຈາກນັ້ນໃຫ້ກວດເບິ່ງມູນຄ່າຂອງດັດຊະນີນັ້ນແລະມູນຄ່າດັດສະນີຕໍ່ໄປຂອງມັນແລະພຽງແຕ່ປ່ຽນຈຸດນັ້ນ. ສຳ ລັບສິ່ງນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະ ນຳ ໃຊ້ຮັງ ໃນຂະນະທີ່ loop ໃນຄັ້ງ ທຳ ອິດໃນຂະນະທີ່ loop. ຫຼັງຈາກນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະຜ່ານມັນຈາກດັດຊະນີປັດຈຸບັນນັ້ນມາເປັນ 0 ແລະຈະເຮັດໃຫ້ມູນຄ່າຂອງດັດຊະນີກາງຫຼຸດລົງ. ພາຍໃນ ໃນຂະນະທີ່ loop, ພວກເຮົາຈະເກັບມູນຄ່າດຽວກັນກັບດັດສະນີປັດຈຸບັນໄປຍັງ swappingIndex ແລະຫຼັງຈາກນັ້ນເອົາຄ່າ swappingIndex ແລະມູນຄ່າຕໍ່ໄປຂອງມັນແລະແລກປ່ຽນມັນ. ສຳ ລັບການແລກປ່ຽນຄັ້ງທີສອງ, ເພີ່ມມູນຄ່າຂອງ swappingIndex ແລະເຮັດການແລກປ່ຽນ ສຳ ລັບ swappingIndex ແລະຄ່າດັດຊະນີຕໍ່ໄປ.

ສຳ ລັບຄວາມແຕກຕ່າງຕໍ່ໄປ, ພວກເຮົາຈະຫຼຸດຄ່າຂອງດັດຊະນີກາງ. ເພື່ອວ່າມັນສາມາດເອົາຄ່າຕ່າງໆຈາກດ້ານ ໜ້າ ຂອງອາເລ. ເຊັ່ນດຽວກັນ, ການນັບແລະ swappingIndex ຈະຄືກັນກັບມູນຄ່າຂອງມູນຄ່າດັດຊະນີກາງທີ່ພວກເຮົາຫຼຸດລົງເພື່ອຂ້າມມູນຄ່າກ່ອນ ໜ້າ ຂອງອາເລ. ຫຼັງຈາກການແລກປ່ຽນທັງ ໝົດ ທີ່ພວກເຮົາໄດ້ເຮັດແລ້ວ, ພວກເຮົາຈະລົງພິມແຖວນັ້ນ, ແລະຕົວເລກທັງ ໝົດ ຈະຖືກປ່ຽນເປັນແບບຢ່າງ.

ລະຫັດ

ລະຫັດ C ++ ເຖິງຕົວເລກ Shuffle 2n ເປັນຕົວເລກ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມ

#include<iostream>
using namespace std;

void shuffleInt(int arr[], int n)
{
    if (arr == NULL || n % 2 == 1)
        return;

    int middleIndex = (n - 1) / 2;

    while (middleIndex > 0)
    {
        int countIndex = middleIndex, swappingIndex = middleIndex;

        while (countIndex -- > 0)
        {
            int temp = arr[swappingIndex + 1];
            arr[swappingIndex + 1] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            swappingIndex++;
        }
        middleIndex--;
    }
}
int main()
{
    int arr[] = {1, 9, 25, 4, 16, 36};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffleInt(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i]<<" ";
}
1 4 9 16 25 36

ລະຫັດ Java ກັບຕົວເລກ Shuffle 2n ເປັນ a1-b1-a2-b2-a3-b3 - .. bn ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມ

class Shuffle2nIntegers
{
    public static void shuffleInt(int[] arr)
    {

        if (arr == null || arr.length % 2 == 1)
            return;

        int middleIndex = (arr.length - 1) / 2;


        while (middleIndex > 0)
        {
            int countIndex = middleIndex, swappingIndex = middleIndex;

            while (countIndex -- > 0)
            {
                int temp = arr[swappingIndex + 1];
                arr[swappingIndex + 1] = arr[swappingIndex];
                arr[swappingIndex] = temp;
                swappingIndex++;
            }
            middleIndex--;
        }
    }

    public static void main(String[] args)
    {
        int arr[] = {1, 9, 25, 4, 16, 36};
        shuffleInt(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print( arr[i]+" ");
        System.out.println();
    }
}
1 4 9 16 25 36

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

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

O (n ^ 2) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນແຕ່ລະຄັ້ງທີ່ພວກເຮົາ ກຳ ລັງຫຼຸດລົງກາງຂອງ MidIndex ໂດຍ ໜຶ່ງ. ແຕ່ວ່າວົງມົນພາຍໃນເຮັດວຽກເປັນ ຈຳ ນວນເວລາກາງຂອງ ຈຳ ນວນກາງ. ທ່ານສາມາດພິຈາລະນາມັນເປັນສອງວົງແຫວນແບບງ່າຍໆທີ່ loop ນອກແລ່ນຈາກ i = 0 ເຖິງ n ວົງພາຍໃນແລ່ນຈາກ i + 1 ເຖິງ. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາແມ່ນຫຼາຍຂະ ໜາດ.

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

ໂອ (1), ເພາະວ່າສູດການຄິດໄລ່ແມ່ນວິທີແກ້ໄຂໃນສະຖານທີ່. ນັ້ນແມ່ນການປະຕິບັດງານທັງ ໝົດ ທີ່ ກຳ ລັງ ດຳ ເນີນຢູ່ແມ່ນການປ່ຽນແທນອົງປະກອບຂອງອາເລໃນເບື້ອງຕົ້ນ. ແລະອາຄານ ໃໝ່ ໃດໆກໍ່ບໍ່ໄດ້ເຮັດ.