അധിക ഇടം ഉപയോഗിക്കാതെ 2n പൂർണ്ണസംഖ്യകളെ a1-b1-a2-b2-a3-b3 - .. bn ആയി ഷഫിൾ ചെയ്യുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ഡി.ഇ.ഷാ ബൈ ഫനാറ്റിക്സ് തീർച്ചയായും പേ
അറേ ഭിന്നിപ്പിച്ചു കീഴടക്കുക റിക്കറിഷൻ

പ്രശ്നം പ്രസ്താവന

നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി 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 പൂർണ്ണസംഖ്യ.  എല്ലാ സംഖ്യ മൂല്യങ്ങളും, പ്രത്യേകിച്ച് നൽകിയിരിക്കുന്ന രീതിയിൽ മാറ്റാൻ ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. ഞങ്ങൾ അറേയുടെ പകുതി മാത്രമേ സഞ്ചരിക്കുകയുള്ളൂ. അൽ‌ഗോരിതം അനുസരിച്ച് വരുന്ന എല്ലാ മൂല്യങ്ങളും മാറ്റുന്നു. ആദ്യം, ശ്രേണി ശൂന്യമായിരിക്കരുത് എന്ന് ഞങ്ങൾ പരിശോധിക്കാൻ പോകുന്നു. ഉത്തരം, അറേയുടെ നീളം തുല്യമായിരിക്കണം. അതിനാലാണ് അറേകളുടെ ദൈർഘ്യം വിചിത്രമായിരിക്കരുത് എന്ന അവസ്ഥ ഞങ്ങൾ പരിശോധിക്കുന്നത്. മുകളിൽ സൂചിപ്പിച്ച ഏതെങ്കിലും നിബന്ധനകൾ തെറ്റാണെങ്കിൽ, അത് ഒരു produce ട്ട്‌പുട്ട് നൽകില്ല.

ഞങ്ങൾ അറേയുടെ മധ്യ സൂചിക കണ്ടെത്തുകയും ആ സൂചികയുടെ മൂല്യവും അതിന്റെ അടുത്ത സൂചിക മൂല്യവും പരിശോധിക്കുകയും അത് സ്വാപ്പ് ചെയ്യുകയും ചെയ്യും. അതിനായി ഞങ്ങൾ നെസ്റ്റഡ് ഉപയോഗിക്കാൻ പോകുന്നു ലൂപ്പ് സമയത്ത് ആദ്യ സമയത്ത് ലൂപ്പിൽ. നിലവിലെ സൂചികയിൽ നിന്ന് 0 ലേക്ക് സഞ്ചരിച്ച് മധ്യ സൂചികയുടെ മൂല്യം കുറയ്‌ക്കാൻ ഞങ്ങൾ പോകുന്നു. ആന്തരികത്തിനുള്ളിൽ ലൂപ്പ് സമയത്ത്, നിലവിലെ സൂചികയുടെ അതേ മൂല്യം സ്വാപ്പിംഗ് ഇൻഡെക്സിലേക്ക് ഞങ്ങൾ സംഭരിക്കുകയും തുടർന്ന് സ്വാപ്പിംഗ് ഇൻഡെക്സ് മൂല്യവും അതിന്റെ അടുത്ത മൂല്യവും എടുത്ത് സ്വാപ്പ് ചെയ്യുകയും ചെയ്യും. രണ്ടാമത്തെ സ്വാപ്പിനായി, സ്വാപ്പിംഗ് ഇൻഡെക്സിന്റെ മൂല്യം വർദ്ധിപ്പിച്ച് നിലവിലെ സ്വാപ്പിംഗ് ഇൻഡെക്സിനും അതിന്റെ അടുത്ത സൂചികയുടെ മൂല്യത്തിനും വേണ്ടി സ്വാപ്പിംഗ് ചെയ്യുക.

അടുത്ത ട്രാവെർസലിനായി, മധ്യ സൂചികയുടെ മൂല്യം ഞങ്ങൾ കുറയ്ക്കും. അതിന് അറേയുടെ മുന്നിൽ നിന്ന് മൂല്യങ്ങൾ എടുക്കാൻ കഴിയും. അതുപോലെ, എണ്ണവും സ്വാപ്പിംഗ് ഇൻഡെക്സും മധ്യ സൂചിക മൂല്യത്തിന്റെ മൂല്യത്തിന് തുല്യമായിരിക്കും, അത് അറേയുടെ മുമ്പത്തെ മൂല്യങ്ങൾ മറികടക്കാൻ ഞങ്ങൾ കുറച്ചിരുന്നു. ഞങ്ങൾ‌ ചെയ്‌ത എല്ലാ സ്വാപ്പിംഗിനും ശേഷം, ഞങ്ങൾ‌ ആ അറേ പ്രിന്റുചെയ്യാൻ‌ പോകുകയാണ്, മാത്രമല്ല എല്ലാ അക്കങ്ങളും ഒരു നിശ്ചിത രീതിയിൽ‌ മാറ്റുകയും ചെയ്യും.

കോഡ്

അധിക ഇടം ഉപയോഗിക്കാതെ 2 ++ സംഖ്യകളെ 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

അധിക ഇടം ഉപയോഗിക്കാതെ a2-b1-a1-b2-a2-b3 - .. bn ആയി 3n പൂർണ്ണസംഖ്യകളിലേക്കുള്ള ജാവ കോഡ്

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 = 0 മുതൽ n വരെ പ്രവർത്തിക്കുന്ന ലളിതമായ രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകളായി നിങ്ങൾക്ക് ഇതിനെ കണക്കാക്കാം. ആന്തരിക ലൂപ്പ് i + 1 മുതൽ പ്രവർത്തിക്കുന്നു. അങ്ങനെ സമയ-സങ്കീർണ്ണത പോളിനോമിയലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം അൽ‌ഗോരിതം ഒരു സ്ഥലത്തുള്ള അൽ‌ഗോരിതം ആണ്. പ്രാരംഭ അറേ ഘടകങ്ങളെ മാറ്റിസ്ഥാപിക്കുകയാണ് എല്ലാ പ്രവർത്തനങ്ങളും. പുതിയ അറേകളൊന്നും നിർമ്മിച്ചിട്ടില്ല.