다음 순열

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance Facebook 팩트 셋 Flipkart 구글 Microsoft 모건 스탠리 (Morgan Stanley) 세일즈 포스 동네 짱
조회수 111

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

다음 순열 문제에서 우리는 단어를 제공했습니다. 사 전적으로 더 큰 순열을 찾으십시오.

input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

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

사전 순서

사전에 배열 된 단어의 모든 순열, 이렇게 얻은 단어의 순서를 사전 순이라고합니다.

전의:

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

act
atc
cat
cta
tac
tca

우리는 '고양이'가 '행동'보다 사 전적으로 더 크다는 것을 알 수 있습니다.

다음 순열을위한 알고리즘

내림차순으로 완전히 정렬 된 단어의 경우, 예 : "nmhgfedcba"에는 다음 순열이 없습니다. 내림차순으로 완전히 정렬되지 않은 단어의 다음 순열을 찾을 수 있습니다. 예 :“nmhdgfecba”. 아래는 연산:
주어진 값 : str =“nmhdgfecba”

  1. 문자열의 오른쪽에서 순회하여 내림차순을 따르지 않는 첫 번째 문자를 찾습니다. str의 'd'는 내림차순을 따르지 않습니다. 'd'의 인덱스 = 3.
  2. 'd'오른쪽에서 ASCII 값의 'd'보다 더 큰 (또는 가장 가까운) 문자를 검색합니다. [nmhd] gfecba의 'e'는 'd'보다 큽니다.이 작업은 binarySearch () 함수를 사용하여 수행됩니다.
  3. 'e'와 'd'를 바꾸십시오. 결과 문자열은“nmhegfdcba”입니다.
  4. 이제 1 단계에서 찾은 인덱스 이후에 발생하는 결과 문자열의 일부를 뒤집습니다 (reverse () 함수를 사용하여 수행). "gfdcba"를 뒤집고 기본 문자열에 다시 추가합니다.
  5. output =“nmheabcdfg”,“nmhgfedcba”의 사전 식 다음 순열입니다.  다음 순열

다음 순열을위한 구현

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

자바 프로그램

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

STL 라이브러리를 사용한 다음 순열

STL 라이브러리 C + + 주어진 문자열의 다음 순열을 생성하는 함수 next_permutation () 포함

#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

복잡성 분석

  1. 시간 복잡성: 전체 시간 복잡도 T (n) = O (n)
    • 최악의 경우 nextPermutation ()의 첫 번째 단계는 O (n) 시간이 걸립니다.
    • binarySearch ()는 O (logn) 시간이 걸립니다.
    • reverse ()는 O (n) 시간이 걸립니다.
  2. 공간 복잡성: A (n) = O (1) 여기서는 작업 계산 중에 보조 공간을 사용하지 않기 때문입니다. 즉,이 경우 다음 순열 문제의 공간 복잡도는 일정합니다.

참고

균열 시스템 설계 인터뷰
Translate »