an-b2-a1-b1-a2-b2 - .. bn اضافی جگہ استعمال کیے بغیر bn 3 عددی اجزا کو شفل کریں  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ڈی ای شا Expedia فانٹکس بے شک پی پی یو
لڑی تقسیم اور فتح تکرار

مسئلہ یہ بیان  

آپ کو ایک دیا جاتا ہے صف of اشارے. مسئلہ "A2-b1-a1-b2-a2-b3 - .. کے طور پر اضافی جگہ کا استعمال کیے بغیر BN" کے تبادلہ 3n اشارے کو صفوں میں تبدیل کرنے کے لئے کہتا ہے جیسے نمبر (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 میں کیا جائے گا۔

an-b2-a1-b1-a2-b2 - .. bn اضافی جگہ استعمال کیے بغیر bn 3 عددی اجزا کو شفل کریں

الگورتھم سے شفل 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 عدد  اس کے بعد ہم سے کہا جاتا ہے کہ وہ پوری طرح کی پوری اقدار کو خاص طور پر دیئے گئے انداز میں بدلیں۔ ہم صرف آدھے صف کو عبور کریں گے۔ اور الگورتھم کے مطابق آنے والی تمام اقدار کو تبدیل کرنا۔ پہلے ، ہم یہ چیک کرنے جارہے ہیں کہ صف صفایا نہیں ہونا چاہئے۔ جواب میں ، صف کی لمبائی بھی برابر ہونی چاہئے۔ اسی لئے ہم اس حالت کی جانچ کرتے ہیں کہ صفوں کی لمبائی عجیب نہیں ہونی چاہئے۔ اگر مذکورہ بالا شرائط میں سے کوئی بھی غلط ہے ، تو یہ آؤٹ پٹ تیار نہیں کرے گا۔

یہ بھی دیکھتے ہیں
کرداروں کو دہرانے کے بغیر سب سے طویل سبسٹریننگ

ہم صف کے مڈل انڈیکس کا پتہ لگائیں گے اور پھر اس انڈیکس کی قدر اور اس کی اگلی انڈیکس ویلیو کی جانچ کریں گے اور اسے آسانی سے تبدیل کریں گے۔ اس کے لئے ، ہم نےسٹڈ کو استعمال کرنے جارہے ہیں جبکہ لوپ پہلی جبکہ لوپ میں پھر ہم اسے موجودہ انڈیکس سے 0 تک لے جانے والے ہیں اور درمیانی انڈیکس کی قدر کو کم کرتے رہیں گے۔ اندرونی اندر جبکہ لوپ، ہم ایک ہی قدر کو موجودہ انڈیکس کی حیثیت سے اسٹاپنگ انڈیکس میں ذخیرہ کریں گے اور پھر اسکیپنگ انڈیکس ویلیو اور اس کی اگلی قیمت لیں گے اور اسے تبدیل کریں گے۔ دوسرے تبادلے کے ل sw ، سوئپنگ انڈیکس کی قدر میں اضافہ کریں اور موجودہ سویپنگ انڈیکس اور اس کے اگلے اشاریہ کی قدر کے ل sw تبادلہ کریں۔

اگلے گزرنے کے لal ، ہم مڈل انڈیکس کی قدر کو کم کردیں گے۔ تاکہ یہ صفوں کے سامنے سے اقدار لے سکے۔ اسی طرح ، گنتی اور تبادلہ انڈیکس درمیانی اشاریہ کی قدر کی طرح ہوگا جو ہم صف کی پہلے والی اقدار کو عبور کرنے میں کم ہوگئے ہیں۔ ہم نے جو تبادلہ کیا ہے اس کے بعد ، ہم اس صف کو پرنٹ کرنے جا رہے ہیں ، اور تمام نمبروں کو ایک مخصوص انداز میں تبدیل کردیا جائے گا۔

ضابطے  

A +-b2-a1-b1-a2-b2 کے طور پر سی ++ کوڈ میں 3n انفرز کو شفل کریں - .. اضافی جگہ استعمال کیے بغیر 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 اضافی جگہ استعمال کیے بغیر

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) کہاں "این" صف میں عناصر کی تعداد ہے۔ جیسا کہ ہر بار ہم مڈل انڈیکس کو ایک ایک کرکے کم کررہے ہیں۔ لیکن اندرونی لوپ مڈل انڈیکس متعدد بار چلتا ہے۔ آپ اسے سادہ دو گھونسلے والے لوپوں پر غور کرسکتے ہیں جہاں بیرونی لوپ i = 0 سے n اندرونی لوپ i + 1 سے چلتا ہے۔ اس طرح وقت کی پیچیدگی کثیر الجہتی ہے۔

یہ بھی دیکھتے ہیں
2D میٹرکس میں زیادہ سے زیادہ رقم کا مستطیل

خلائی پیچیدگی

O (1) ، کیونکہ الگورتھم ایک جگہ الگورتھم ہے۔ یہ وہ ساری کاروائیاں ہیں جو ابتدائی صف عناصر کی جگہ لے رہی ہیں۔ اور کوئی نئی آرے نہیں بنی ہیں۔