Następna permutacja

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Facebook Zestaw faktów Flipkart Google Microsoft Morgan Stanley Salesforce Uber
sznurodwiedzajacy 115

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W następnym zadaniu z permutacją podaliśmy słowo, znajdź jego leksykograficznie większą_permutację.

Przykład

input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

input : str = "spoonfeed"
output : Next Permutation Doesnt exist

Porządek leksykograficzny

W przypadku wszystkich permutacji słowa uporządkowanego w słowniku kolejność otrzymanych w ten sposób słów nazywana jest porządkiem leksykograficznym.

ex:

word = 'cat'
lexicographical order of permutations of 'cat' : 

act
atc
cat
cta
tac
tca

widzimy, że „kot” jest leksykograficznie większy niż „akt”.

Algorytm dla następnej permutacji

W przypadku słowa, które jest całkowicie posortowane w porządku malejącym, np. „Nmhgfedcba” nie ma następnej permutacji. Możemy znaleźć następną permutację słowa, które nie jest całkowicie posortowane w porządku malejącym. np. „nmhdgfecba”. Poniżej znajduje się plik algorytm:
Biorąc pod uwagę: str = "nmhdgfecba"

  1. Przejdź z prawej strony ciągu i poszukaj pierwszego znaku, który nie występuje w kolejności malejącej. „d” w str nie ma kolejności malejącej. indeks „d” = 3.
  2. Po prawej stronie litery „d” wyszukaj znak, który jest tylko (lub najbliższy) większy niż „d” w wartości ASCII. 'e' w [nmhd] gfecba jest po prostu większe niż 'd'. Robi się to za pomocą funkcji binarySearch ().
  3. zamień 'e' i 'd'. Wynikowy ciąg to „nmhegfdcba”.
  4. Teraz odwróć (za pomocą funkcji reverse ()) część wynikowego ciągu występującą po indeksie znalezionym w kroku 1. Odwróć „gfdcba” i dołącz go z powrotem do głównego ciągu.
  5. output = „nmheabcdfg”, jest leksykograficznie następną permutacją „nmhgfedcba”.  Następna permutacjaszpilka

Implementacja do następnej permutacji

Program w C ++

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

// function to reverse the string between index l and r
void reverse(string &str,int l,int r)
{
    while(l < r)
    swap(str[l++],str[r--]);
}

// function to search a character lying between index l and r 
// which is closest greater (just greater) than val
// and return it's index 
int binarySearch(string& str,int l,int r,char val) 
{ 
  int index = -1; 
  
  while (l <= r) 
  { 
    int mid = (l+r)/2;
    if (str[mid] <= val) 
    {
        r = mid - 1;
    }
    else 
    { 
      l = mid + 1; 
      if (index == -1 || str[index] >= str[mid]) 
        index = mid; 
    } 
  } 
  return index; 
} 

// this function generates next permutation (if there exists any such permutation) from the given string
// and returns True
// Else returns false
bool nextPermutation(string& str) 
{ 
  int len = str.length();
  int i = len-2; 
  
  while (i >= 0 && str[i] >= str[i+1]) 
  i--;
  
  if (i < 0) 
    return false; 
  else 
  { 
    int index = binarySearch(str,i+1,len-1,str[i]); 
    swap(str[i],str[index]); 
    reverse(str,i+1,len-1); 
    return true; 
  } 
} 

// main function to find next permutation
int main() 
{ 
  string str = "nmhdgfecba"; 
  bool is = nextPermutation(str); 
  
  if(is == false) 
    cout<< "Next Permutation Doesnt exist" <<endl; 
  else
    cout<<str<<endl; 
    
  return 0; 
} 
nmheabcdfg

Program Java

class permutation
{
    // swap two characters of string 
    static void swap(StringBuilder sb,int l,int r)
    {
        char temp = sb.charAt(l);
        sb.setCharAt(l,sb.charAt(r));
        sb.setCharAt(r,temp);
    }
    
    // function to reverse the string between index l and r
    static void reverse(StringBuilder sb,int l,int r)
    {
        while(l < r)
        {
            swap(sb,l,r);
            l++;
            r--;
        }
    }
    
    // function to search a character lying between index l and r 
    // which is closest greater (just greater) than val
    // and return it's index 
    static int binarySearch(StringBuilder sb,int l,int r,char val) 
    { 
    	int index = -1; 
    	
    	while (l <= r) 
    	{ 
    		int mid = (l+r)/2;
    		if (sb.charAt(mid) <= val) 
    		{
    		    r = mid - 1;
    		}
    		else 
    		{ 
    			l = mid + 1; 
    			if (index == -1 || sb.charAt(index) >= sb.charAt(mid)) 
    				index = mid; 
    		} 
    	} 
    	return index; 
    } 
    
    // this function generates next permutation (if there exists any such permutation) from the given string
    // and returns True
    // Else returns false
    static boolean nextPermutation(StringBuilder sb) 
    { 
    	int len = sb.length();
    	int i = len-2; 
    	
    	while (i >= 0 && sb.charAt(i) >= sb.charAt(i+1)) 
    	i--;
    	
    	if (i < 0) 
    		return false; 
    	else 
    	{ 
    		int index = binarySearch(sb,i+1,len-1,sb.charAt(i)); 
    		swap(sb,i,index); 
    		reverse(sb,i+1,len-1); 
    		return true; 
    	} 
    }    
    
    // main function to find next permutation
    public static void main(String args[])
    {
        String str = "nmhdgfecba";
        // strings in java are immutable,so we convert strings into StringBuilder
        // StringBuilder are mutable strings        
        StringBuilder sb = new StringBuilder(str);

    	boolean is = nextPermutation(sb); 
    	
    	if(is == false) 
    		System.out.println("Next Permutation Doesnt exist"); 
    	else
    		System.out.println(sb);
           
    }
}
nmheabcdfg

Następna permutacja przy użyciu biblioteki STL

Biblioteka STL plików C + + zawiera funkcję next_permutation (), która generuje następną permutację danego ciągu

#include <iostream>
#include <bits/stdc++.h>    // STL library of C++
using namespace std;

int main() 
{
    string str = "nmhdgfecba";
    
    // next_permutation() is present in STL library
    // next_permutation() generates Next Permutation of a string if it exists
    // and returns true
    // else returns false
    if(next_permutation(str.begin(),str.end()))
    cout<<str<<endl;
    else
    cout<<"Next Permutation Doesnt exist";

    return 0;
}
nmheabcdfg

Analiza złożoności

  1. Złożoność czasowa: Całkowita złożoność czasowa T (n) = O (n)
    • W najgorszym przypadku pierwszy krok nextPermutation () zajmuje O (n) czasu.
    • binarySearch () zajmuje O (logn) czasu.
    • reverse () zajmuje O (n) czasu.
  2. Złożoność przestrzeni: A (n) = O (1), ponieważ tutaj nie używamy żadnej dodatkowej przestrzeni podczas obliczania zadania. Oznacza to, że w tym przypadku złożoność przestrzenna następnego problemu permutacji jest stała.

Numer Referencyjny

Wywiady dotyczące projektowania systemu pękania
Translate »