Pancake çeşidlənməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook microsoft kvadrat Über
Geyim çeşidləyiciBaxılıb 284

Problem bəyanat

"Pancake Sorting" problemində bir verdik array A [] tam ədədi. Bir sıra pancake flipslərini yerinə yetirərək serialı sıralayın. Bir pancake flipində aşağıdakı addımları edirik:

  • 1 <= k <= arr.length olduğu bir tam ədəd seçin.
  • [0… k-1] alt dizisini tərsinə çevirin (0 indeksli).

Giriş Formatı

Bir tam ədədi olan ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Arr-nı sıralayan pancake çevirmələrinin ardıcıllığına uyğun k-dəyərlərindən ibarət bir sıra çap edin. Dizini 10 * arr.length () flip arasında sıralayan hər hansı bir etibarlı cavab doğru olaraq qiymətləndiriləcəkdir.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 3
  • 1 <= A [i] <= N
  • A [] dakı bütün ədədlər misilsizdir.

misal

5
3 2 4 1 5
3 4 2 3 2

Pancake çeşidlənməsi üçün alqoritm

Əsas fikir massivdəki maksimum elementi tapmaq və onu massivin sonuna yerləşdirmək və massivin ölçüsünü azaltmaqdır.

Dizinin ölçüsü 1-ə qədər, azalma ölçüsü

1. Cari ölçü massivində maksimum elementi tapın.

2. massivi maksimum saya qədər çevirin, yəni maksimum sayı massivin başlanğıcındadır.

3. İndi cari ölçülü massivi çevirin, yəni maksimum sayı massivin sonundadır.

4. Sıralanmış massivi çap edin.

Həyata keçirilməsi

Pancake Sıralama üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

bool isSorted(vector<int>& arr)
{
    if(arr.size()==0 || arr.size()==1)
    {
        return 1;
    }
    for(int i=1;i<arr.size();i++)
    {
        if(arr[i-1]>arr[i])
        {
            return 0;
        }
    }
    return 1;
}

void flip(vector<int>& arr,int k)
{
    int i=0,j=k-1;
    while(i<j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j] = temp;
        i++;j--;
    }
}
    
vector<int> pancakeSort(vector<int>& arr) {
    vector<int> res;
    int k=0,j=0,index=-1,large=INT_MIN,n=arr.size();
    while(!isSorted(arr))
    {
        for(int i=0;i<n-j;i++)
        {
            if(large<arr[i])
            {
                large=arr[i];
                index=i;
            }
        }
        // bringing the largest values at head
        k=index+1;
        flip(arr,k);
        res.push_back(k);
        // fliping the head value at its sorted place
        k=n-j;
        flip(arr,k);
        res.push_back(k);
        j++;
        large=INT_MIN;
    }
    return res;
}

int main()
{
   int n;
   cin>>n;
   vector<int> v;
   for(int i=0;i<n;i++)
   {
       int x;
       cin>>x;
       v.push_back(x);
   }
   pancakeSort(v);
   for(auto u: v)
   {
       cout<<u<<" ";
   }
   return 0;
}

Pancake Sorting üçün Java Proqramı

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class sum
{
    static void pancakeSort(int A[], int n) 
    {
        List<Integer> ans = new ArrayList<>();
        for (int valueToSort = A.length; valueToSort > 0; valueToSort--) 
        {
            int index = sum.find(A, valueToSort);
            if (index == valueToSort - 1)
                continue;
            if (index != 0) 
            {
                ans.add(index + 1);
                sum.flip(A, index + 1);
            }
            ans.add(valueToSort);
            sum.flip(A, valueToSort);
        }
        for(int i=0;i<n;i++) 
  {
      System.out.print(ans.get(i)+" ");
  }
        System.out.println();
    }
    public static void flip(int[] sublist, int k) 
    {
        int i = 0;
        while (i < k / 2) 
        {
            int temp = sublist[i];
            sublist[i] = sublist[k - i - 1];
            sublist[k - i - 1] = temp;
            i += 1;
        }
    }
    public static int find(int[] a, int target) 
    {
        for (int i = 0; i < a.length; i++)
            if (a[i] == target)
                return i;
        return -1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        pancakeSort(a, n);
    }
}
5 
3 2 4 1 5
3 4 2 3 2

Pancake Sıralama üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n ^ 2) hara n verilmiş massivin ölçüsüdür.

  • Alqoritmdə, ilə bir döngə işlədirik N təkrarlamalar.
  • Hər təkrarlamada siyahının müvafiq prefiksi ilə məşğul oluruq. Burada prefiksin uzunluğunu belə qeyd edirik məsələn birinci təkrarlamada prefiksin uzunluğu N-dir, ikinci təkrarlamada prefiksin uzunluğu N-1.

Kosmik Mürəkkəblik

O (n) hara n verilmiş massivin ölçüsüdür.

  • Alqoritm daxilində, son nəticələrin qorunması üçün pancake flips sayına mütənasib bir siyahı istifadə edirik.
  • Hər təkrarlama dövrü üçün ən çox iki pancake flipsi əlavə edərdik. Bu səbəbdən, lazım olan maksimum pancake flips sayının olması lazımdır .
  • Nəticədə, alqoritmin kosmik mürəkkəbliyi . Biri funksiyanın nəticəsini tutmaq üçün lazım olan yeri nəzərə almırsa, yuxarıdakı alqoritmi sabit bir məkan həlli kimi qəbul etmək olar.
Translate »