एरेलाई Zig-Zag फेसनमा बदल्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एक्सेंचर अमेजन फोरकाइट्स टेराडाटा Xome
एरे

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

समस्या "Zig-Zag फेसन मा एरे रूपान्तरण" भन्छ कि तपाइँ एक दिइएको छ - पूर्णांकको। समस्या कथनले एर्रेलाई zig-zag तरीकामा क्रमबद्ध गर्न सोध्छ कि एर्रेमा एलिमेन्टहरू like जस्तो देखिन्छ।  a <b> c <d> e <f.

उदाहरणका

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

स्पष्टीकरण

Both दुबै १ र २ (यसको छेउछाउको तत्वहरु) भन्दा ठूलो छ, its दुबै यसको नजिकको तत्वहरू भन्दा ठूलो छ, त्यसैले। हो।

अल्गोरिदम

1. Mark flag is equal to true.
2. Traverse the array from 0 to n-2, where n is the length of the array.
  1. Check if the flag is true
    1. Check if the current element is greater than the next element.
      1. Swap those values.
    2. Else, check if the current element is greater than the next element,
      1. Check if the current element is lesser than the next element.
        1. Swap those values.
3. Flip the value of the flag.

स्पष्टीकरण

हामीले एउटा दिएका छौं array of पूर्णांकहरू। हाम्रो कार्य भनेको एर्रेलाई zigzag तरीकाले पुन: व्यवस्थित गर्नु हो। हामीले एउटा सर्त यो पाएका छौं कि नम्बर एलिमेन्ट पनि यसको दुई नजिकको तत्व भन्दा ठूलो हुनुपर्दछ,a <b> c <d> e <f '। हामी यहाँ देख्न सक्छौं कि b र d यसका दुई आसन्न तत्त्वहरू भन्दा ठूला छन्, 'a' र 'c' यसको दुई नजिकको एलिमेन्टहरू भन्दा कम छन्। हाम्रो कार्य भनेको दिईएको एरेलाई यस्तै व्यवस्था गर्नु हो। यसको लागि हामी मानहरू स्वैप गर्न गइरहेका छौं, एरे ट्र्याभर्स गर्ने क्रममा, जुन zigzag तरीकाले क्रमबद्ध छ।

हामी एउटा चिन्ह लगाइनेछौं बूलियन सहीमा मान, तब हामी लूप ट्र्याभर्सिंग गर्न लाग्नेछौं, र जाँच गर्नुहोस् कि झण्डा सत्य हो कि होइन। यदि यो सत्य हो भने, हामी हालको मानको लागि जाँच गर्छौं यदि हालको मान यसको अर्को मान भन्दा ठूलो छ भने। त्यसोभए हामी ती मानहरू बदल्ने छौं। र बुलियन मानलाई गलतमा चिन्ह लगाउनुहोस्। हामीले भर्खरै यसको मान फिर्ता गर्नुपर्नेछ, यदि यो सहि छ भने, यसलाई गलतमा अपडेट गर्नुहोस्, यदि यो गलत छ भने, यसलाई सहीमा अपडेट गर्नुहोस्। त्यसैले हरेक वैकल्पिक traversal को साथ, हरेक पुनरावृत्ति को लागी त्यहाँ बिभिन्न फ्ल्याग मानहरू हुनेछन्। यससँग, केवल एक भाग कार्यान्वयन हुन गइरहेको छ, या त भाग वा अन्य भाग।

उही चीज जुन हामी अर्को अंशसँगै गर्छौं, मानहरु बदल्न। यदि ट्र्याभर्सलमा एर्रेको हालको मान अर्को मानभन्दा कम छ भने। र ट्रान्सभर्ल पछि, हामीले भर्खर एरे प्रिन्ट गर्नुपर्दछ जुनमा हामीले अपडेट गरेका छौं।

एरेलाई Zig-Zag फेसनमा बदल्नुहोस्

 

कोड

C ++ कोड एरिलाई Zig-Zag फेसनमा रूपान्तरण गर्न

#include <iostream>

using namespace std;

void sortZigZag(int arr[], int n)
{
    bool flag = true;

    for (int i=0; i<=n-2; i++)
    {
        if (flag)
        {
            if (arr[i] > arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        else
        {
            if (arr[i] < arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        flag = !flag;
    }
}
int main()
{
    int arr[] = {2,4,5,1,7,6,8};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortZigZag(arr, n);
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}
2 5 1 7 4 8 6

जाभा कोड एरेलाई Zig-Zag फेसनमा रूपान्तरण गर्न

import java.util.Arrays;

class zigzagArray
{
    public static void sortZigZag(int arr[])
    {
        boolean flag = true;

        int temp =0;

        for (int i=0; i<=arr.length-2; i++)
        {
            if (flag)
            {
                if (arr[i] > arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }

            }
            else
            {
                if (arr[i] < arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            if(flag==true)
                flag=false;
            else
                flag=true;
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,5,1,7,6,8};
        sortZigZag(arr);
        System.out.println(Arrays.toString(arr));
    }
}
[2, 5, 1, 7, 4, 8, 6]

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। किनकि हामीले एर्रेमा एलिमेन्टहरू मात्र पार गरेका छौं। समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (१) कुनै अतिरिक्त ठाउँको आवश्यक छ। किनकि हामीले कुनै थप ठाउँ प्रयोग गरेका छैनौं, अन्तरिक्ष जटिलता स्थिर छ।