शापल 2 एन पूर्णांक a1-b1-a2-b2-a3-b3 म्हणून - .. अतिरिक्त जागा वापरल्याशिवाय बीएन


अडचण पातळी मध्यम
वारंवार विचारले अडोब डीई शॉ यामध्ये कट्टरता खरंच पीएयू
अरे विभाजित आणि विजय पुनरावृत्ती

समस्या विधान

आपण एक दिले जाते अॅरे of पूर्णांक. “श्फल 2 एन इंटिजरस ए 1-बी 1-ए 2-बी 2-ए 3-बी 3 म्हणून - .. अतिरिक्त जागा न वापरता बीएन” अशा अ‍ॅरेमधील सर्व संख्या शफल करण्यास सांगते जसे की संख्या (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 मध्ये व्यवस्थित केल्या जातील.

शापल 2 एन पूर्णांक a1-b1-a2-b2-a3-b3 म्हणून - .. अतिरिक्त जागा वापरल्याशिवाय बीएन

अल्गोरिदम ते शफल 2 एन पूर्णांक म्हणून 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 पूर्णांक  नंतर आम्हाला पूर्णांकांची सर्व मूल्ये विशेषतः दिलेल्या पद्धतीने बदलण्यास सांगितले जाते. आम्ही अ‍ॅरेच्या अर्ध्या भागावरच जात आहोत. आणि अल्गोरिदमनुसार आलेल्या सर्व व्हॅल्यूज अदलाबदल. प्रथम आपण हे तपासणार आहोत की अ‍ॅरे रिकामी असू नये. उत्तर देखील, अ‍ॅरेची लांबी समान असणे आवश्यक आहे. म्हणूनच आम्ही अशी स्थिती तपासतो की अ‍ॅरेची लांबी विचित्र असू नये. जर उपरोक्त नमूद केलेली कोणतीही परिस्थिती चुकीची असेल तर ते उत्पादन देणार नाही.

अ‍ॅरेची मधली अनुक्रमणिका शोधू आणि नंतर त्या अनुक्रमणिकेचे मूल्य आणि त्याचे पुढील निर्देशांक मूल्य तपासू आणि त्यास स्वॅप करू. त्यासाठी आम्ही नेस्टेड वापरणार आहोत पळवाट असताना पहिल्या वेळी लूपमध्ये. तर आम्ही त्यास सध्याच्या निर्देशांकातून 0 पर्यंत पाठवित आहोत आणि मध्यम अनुक्रमणिकेचे मूल्य कमी ठेवत आहोत. आतल्या आत पळवाट असतानाआम्ही स्वॅपिंगइन्डेक्स मध्ये वर्तमान निर्देशांकासारखेच मूल्य संग्रहित करू आणि नंतर स्वॅपिंगइन्डेक्स मूल्य आणि त्याचे पुढील मूल्य घेऊ आणि त्यास स्वॅप करू. दुसर्‍या स्वॅपसाठी स्वॅपिंगइन्डेक्सचे मूल्य वाढवा आणि सद्य स्वॅपिंगइन्डेक्स आणि त्यापुढील निर्देशांकातील मूल्य स्वॅपिंग करा.

पुढील ट्रॅव्हर्सलसाठी आम्ही मध्यम निर्देशांकाचे मूल्य कमी करू. जेणेकरून ते अ‍ॅरेच्या पुढच्या भागावर येईल. त्याचप्रमाणे गणना आणि स्वॅपिंगइन्डेक्स मधल्या निर्देशांकाच्या मूल्याइतकेच असेल जे आपण अ‍ॅरेच्या पूर्वीच्या मूल्यांना मागे टाकत कमी होतो. आम्ही पूर्ण केलेल्या अदलाबदलीनंतर आपण तो अ‍ॅरे प्रिंट करू आणि सर्व संख्या दिलेल्या पद्धतीने बदलल्या जातील.

कोड

सी ++ कोड 2-बी 1-ए 1-बी 2-ए 2-बी 3 म्हणून शफल 3 एन पूर्णांक - .. अतिरिक्त जागा न वापरता बीएन

#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

जावा कोडला शफल 2 एन पूर्णांक म्हणून ए 1-बी 1-ए 2-बी 2-ए 3-बी 3 - .. अतिरिक्त जागा वापरल्याशिवाय बीएन

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन ^ 2) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. प्रत्येक वेळी आम्ही एक एक करून मध्यमसूची कमी करत आहोत. पण आतील लूप मधल्या इंडेक्ससाठी किती वेळा चालते. आपण ते सोप्या दोन नेस्टेड लूप्स म्हणून विचार करू शकता जेथे बाह्य लूप i = 0 ते n अंतर्गत आतील लूप i + 1 ते चालते. म्हणून वेळ-गुंतागुंत बहुवचन असते.

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण अल्गोरिदम ही एक जागा-अल्गोरिदम आहे. सुरु असलेल्या अ‍ॅरे घटकांची जागा घेत असलेल्या सर्व ऑपरेशन्स आहेत. आणि नवीन अ‍ॅरेपैकी कोणतेही बनविलेले नाहीत.