Shlle 2n पूर्णांक a1-b1-a2-b2-a3-b3 को रूपमा - .. bn अतिरिक्त खाली ठाउँ प्रयोग नगरी


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब डे श Expedia कट्टरपन्थी वास्तवमा PayU
एरे विभाजित र विजय गर्नुहोस् पुनरावृत्ति

समस्या वक्तव्य

तपाईंलाई एक दिइन्छ array of पूर्णांकहरू। समस्या "shfle 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

स्पष्टीकरण

यदि हामी पहिलो तीनबाट x०, x0, x1 जस्तै तुलना गर्छौं र अर्को तीन नम्बर y2, y0, y1 जस्तै हुनेछ, र यो x2, y0, x0, y1, x1, y2 मा व्यवस्थित हुनेछ।

Shlle 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 पूर्णांक  त्यसोभए हामीलाई सबै पूर्णांक मानहरू विशेष रूपमा दिइएको तरिकामा शफल गर्न भनियो। हामी एर्रेको मात्र आधा ट्र्याभर्सिंग हुनेछौं। र सबै मान बदल्दै जो एल्गोरिथ्मको अनुसार आउँछ। पहिले, हामी जाँच्दै छौं कि एरे खाली हुनु हुँदैन। उत्तर पनि, एर्रे को लम्बाई समान हुनुपर्छ। त्यसकारण हामी सर्तहरू जाँच गर्छौं जुन एरे लम्बाइ अनौठो हुनुहुन्न। यदि माथिका कुनै पनि शर्तहरू गलत छन् भने, यसले आउटपुट उत्पादन गर्दैन।

हामी एर्रेको मध्य सूचकांक फेला पार्नेछौं र त्यसपछि त्यो सूचकांकको मान र यसको अर्को अनुक्रमणिका मान जाँच गर्नेछौं र त्यसलाई स्वैप गर्दछौं। त्यसका लागि, हामी नेस्टेड प्रयोग गर्न गइरहेका छौं जबकि लुप लूपमा पहिलो त्यसो भए हामी त्यसलाई हालको सूचकांकबाट ० मा ट्र्यावर्स गर्न जानेछौं र मध्यम अनुक्रमणिकाको मान घट्दै राख्नेछौं। भित्री भित्र जबकि लुप, हामी swapingIndex मा हालको इन्डेक्सको रूपमा समान मान भण्डार गर्नेछौं र त्यसपछि स्व्यापिंगइन्डेक्स मान र यसको अर्को मान लिन्छौं र यसलाई स्वॅप गर्दछौं। दोस्रो स्वपको लागि, स्व्यापिंगइन्डेक्सको मान बढाउनुहोस् र हालको स्व्यापिंगइन्डेक्स र यसको अर्को सूचकांकको मानको लागि स्व्यापिंग गर्नुहोस्।

अर्को traversal को लागी, हामी मध्य सूचकांकको मान कम गर्नेछौं। ताकि यसले एर्रेको अगाडिबाट मानहरू लिन सक्दछ। त्यस्तै गरी, काउन्ट र स्व्यापिंगइन्डेक्स मध्य इन्डेक्स मानको मान बराबर हुनेछ जुन हामीले एर्रेको पहिलेका मानहरू पार गर्न कम ग to्यौं। हामीले गरेको सबै स्वप्याप पछि, हामी त्यो एर्रे प्रिन्ट गर्न जानेछौं, र सबै नम्बरहरू निश्चित तरिकाले फेरबदल हुनेछन्।

कोड

C ++ कोड Shlle 2n पूर्णा a्क 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

जाभा कोड shlle 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" एर्रेमा एलिमेन्ट्सको संख्या हो। प्रत्येक पटकको रूपमा हामी एक एक गरी मिडलइन्डडेक्स घटाउँदैछौं। तर भित्री लूप मिडियाइन्डिक्स पटक संख्याको लागि दौडन्छ। तपाईं यसलाई साधारण दुई नेस्टेड लूपहरूको रूपमा विचार गर्न सक्नुहुनेछ जहाँ बाह्य लूप i = ० देखि n भित्री लूप i + १ देखि चल्दछ। त्यसैले समय-जटिलता बहुपद हो।

ठाउँ जटिलता

O (१), किनभने एल्गोरिथ्म एक स्थानको एल्गोरिथ्म हो। ती सबै अपरेशनहरू जुन सुरू भइरहेका छन् सुरुको एरे एलिमेन्टहरू बदल्दै छन्। र कुनै नयाँ एरे बनाइएको छैन।