Əlavə yer istifadə etmədən 2n ədədi a1-b1-a2-b2-a3-b3 - .. bn kimi qarışdırın.

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic DE Şou Expedia Fanatics Həqiqətən PayU
Geyim Bölün və fəth edin RecursionBaxılıb 41

Problem bəyanat

Sizə verilir array of tamsayılar. "2n tam ədədi a1-b1-a2-b2-a3-b3 - .. bn kimi boşluq istifadə etmədən qarışdırın" problemi (x0, x1, x2, x3, y0, y1, y2, y3) bu şəkildə x0, y0, x1, y1, x2, y2, x3, y3 və s. kimi qarışdırılacaqdır.

misal

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

Izahat

İlk üç rəqəmdən müqayisə etsək x0, x1, x2, sonrakı üç ədəd y0, y1, y2 kimi olacaq və x0, y0, x1, y1, x2, y2 şəklində yerləşəcəkdir.

Əlavə yer istifadə etmədən 2n ədədi a1-b1-a2-b2-a3-b3 - .. bn kimi qarışdırın.Pin

2n tam ədədi əlavə yer istifadə etmədən a1-b1-a2-b2-a3-b3 - .. bn kimi qarışdırmaq üçün alqoritm

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.

Izahat

Biz verdik array of tam.  Sonra bütün tam dəyərləri, xüsusən də verilmiş şəkildə qarışdırmamız istənir. Dizinin yalnız yarısını keçəcəyik. Və alqoritmə uyğun gələn bütün dəyərləri dəyişdirmək. Əvvəlcə serialın boş olmamasını yoxlayacağıq. Cavab olaraq, massivin uzunluğu bərabər olmalıdır. Buna görə də massivlərin uzunluğunun tək olmaması şərtini yoxlayırıq. Yuxarıda göstərilən şərtlərdən hər hansı biri səhvdirsə, nəticə çıxarmaz.

Dizinin orta indeksini tapacağıq, sonra həmin indeksin dəyərini və növbəti indeks dəyərini yoxlayacağıq və sadəcə dəyişdirək. Bunun üçün yuvadan istifadə edəcəyik döngə zamanı ilk isə loop. Sonra onu indiki indeksdən 0-a keçirək və orta indeksin dəyərini azaltmağa davam edəcəyik. İçəridə döngə zamanı, cari indekslə eyni dəyəri swappingIndex-ə saxlayacağıq, sonra swappingIndex dəyərini və növbəti dəyərini götürüb dəyişdirəcəyik. İkinci mübadilə üçün swappingIndex dəyərini artırın və cari swappingIndex və növbəti indeksin dəyəri üçün dəyişdirin.

Növbəti keçid üçün orta indeksin dəyərini azaldacağıq. Dəyərləri massivin ön hissəsindən götürə bilməsi üçün. Eynilə, count və swappingIndex, dizinin əvvəlki dəyərlərini keçmək üçün azaldığımız orta İndeks dəyərinin dəyəri ilə eyni olacaq. Gördüyümüz bütün mübadilə etdikdən sonra həmin seriyanı çap edəcəyik və bütün rəqəmlər müəyyən bir şəkildə qarışdırılacaq.

Kodu

Əlavə yer istifadə etmədən 2n tam ədədi a1-b1-a2-b2-a3-b3 - .. bn kimi qarışdırmaq üçün C ++ kodu

#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

Əlavə yer istifadə etmədən 2n tam ədədi a1-b1-a2-b2-a3-b3 - .. bn kimi qarışdırmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) hara "N" massivdəki elementlərin sayıdır. Hər dəfə ortaIndex-i bir dəfəyə endiririk. Ancaq daxili döngə middleIndex sayında işləyir. Xarici döngənin i = 0-dan n-yə daxili döngənin i + 1-dən keçdiyinə qədər sadə iki iç içə döngə hesab edə bilərsiniz. Beləliklə, zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (1), çünki alqoritm yerində olan bir alqoritmdir. Edilən bütün əməliyyatlar ilkin sıra elementlərini əvəz edir '. Və yeni massivlərdən heç biri edilmir.

Translate »