Нэмэлт зай ашиглахгүйгээр 2n бүхэл тоог a1-b1-a2-b2-a3-b3 - .. bn гэж холино.


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe DE Шоу Expedia Фанатикууд Үнэндээ PayU
Array Хуваагаад, ялж байна Сэтгэгдэл бичих

Асуудлын мэдэгдэл

Танд массив of бүхэл тоо. "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.

Тайлбар

Бид өгсөн массив of бүхэл тоо.  Дараа нь бид бүхэл тоон утгыг, ялангуяа өгөгдсөн байдлаар холихыг шаардана. Бид массивын талыг л туулах болно. Алгоритмын дагуу ирсэн бүх утгыг солих. Нэгдүгээрт, массив нь хоосон байх ёсгүй гэдгийг шалгах гэж байна. Ans бас массивын урт тэгш байх ёстой. Тиймээс массивын урт сондгой байж болохгүй гэсэн нөхцлийг бид шалгаж байгаа юм. Хэрэв дээр дурдсан нөхцлүүдийн аль нэг нь хуурамч байвал энэ нь үр дүн гарахгүй.

Бид массивын дунд индексийг олж, дараа нь тухайн индексийн утга болон түүний дараагийн индексийн утгыг шалгаад үүнийг сольж солино. Үүний тулд бид үүрээ ашиглах болно while давталт эхний while давталт. Дараа нь бид үүнийг одоогийн индексээс 0 болгож, дунд индексийн утгыг бууруулсаар байх болно. Дотор нь while давталт, бид swappingIndex-т одоогийн индекстэй ижил утгыг хадгалаад swappingIndex утга болон түүний дараагийн утгыг аваад swap хийнэ. Хоёр дахь свопын хувьд swappingIndex-ийн утгыг нэмэгдүүлж, одоогийн swappingIndex болон түүний дараагийн индексийн утгыг солих хэрэгтэй.

Дараагийн давталтын хувьд бид дунд индексийн утгыг бууруулна. Энэ нь массивын урд талын утгуудыг авах боломжтой байх ёстой. Үүнтэй адил тоолох, солиход Индекс нь массивын өмнөх утгуудыг туулахын тулд багасгасан дунд индексийн утгатай ижил байх болно. Бүх солилцоог хийсний дараа бид энэ массивыг хэвлэх бөгөөд бүх тоонуудыг өгөгдсөн байдлаар холих болно.

код

C ++ кодыг нэмэлт зай ашиглахгүйгээр 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

2n бүхэл тоонуудыг a1-b1-a2-b2-a3-b3 - .. bn гэж холих Java кодыг нэмэлт зай ашиглахгүйгээр.

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-ийг нэгээр бууруулж байна. Гэхдээ дотоод гогцоо нь middleIndex-ийн тоогоор ажилладаг. Гаднах гогцоо нь i = 0-ээс n, дотоод гогцоо нь i + 1-ээс үргэлжилдэг энгийн хоёр үүрлэсэн гогцоо гэж үзэж болно. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь олон гишүүнт юм.

Сансрын нарийн төвөгтэй байдал

O (1), Учир нь алгоритм нь байрандаа тавигдсан алгоритм юм. Хийж байгаа бүх үйлдлүүд нь массивын эхний элементүүдийг орлож байгаа юм. Шинэ массивуудын аль нь ч хийгдээгүй байна.