주어진 숫자를 배열하여 가장 큰 숫자를 만듭니다.

난이도 쉽게
자주 묻는 질문 아마존 MakeMyTrip Paytm 조호 (Zoho)
배열 조회수 97

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

문제 정책

정수 배열이 있다고 가정합니다. "가장 큰 숫자를 형성하기 위해 주어진 숫자를 배열"문제는 배열의 숫자로 만들 수있는 최대 값이 출력이되도록 배열을 재 배열하도록 요구합니다.

[34, 86, 87, 765]
878676534

설명 : 우리는 가장 높은 값을 생성하도록 서로 숫자를 연결했습니다. 우리는 가장 큰 값이 765이지만 그것을 제시하면 출력은 지금 우리가 얻은 값보다 작을 것이므로 먼저 87을 취한 다음 86을 취한 다음 휴식을 취해야합니다. 결과는 나머지 숫자로 시작해야합니다.

주어진 숫자를 배열하여 가장 큰 숫자를 형성하는 알고리즘

1 Compare and check which value is lexicographically greater.
2. The greater value will put forward.
3. Return that value.

설명

우리는 배열의 숫자 내에서 모든 숫자가 집합 적으로 배열의 숫자로 형성 될 수있는 가장 큰 숫자를 생성하도록 배열을 재 배열하도록 요청 받았습니다. 그래서 여기서 우리는 입력을 숫자의. 숫자가 주어지면 쉽게 문자열로 변환 할 수 있습니다. 발생하는 문제는 모든 숫자가 연결되었을 때 더 큰 숫자를 찾는 방법입니다. 세 자리 숫자는 두 자리 숫자와 비교할 때 확실히 더 큰 숫자이기 때문입니다. 그러나 여기서 우리는 숫자의 첫 번째 숫자가 입력 된 숫자보다 커야합니다. 이런 식으로 우리는이 문제를 해결할 것입니다.

문자열 조작을 위해 비교 방법을 사용할 것입니다. 이를 통해 수동으로 종류 어휘 학적으로 입력합니다. 이것은 시작 숫자가 시작 숫자가 더 낮은 다른 숫자보다 큰 경우를 의미합니다. 그런 다음 시작 숫자가 더 큰 것을 먼저 넣습니다. 그런 다음 이러한 방식으로 모든 입력을 정렬해야합니다. 이제 언어의 사전 정의 된 방법 인 비교 방법을 사용하여이를 수행하거나 각 문자열을 순회하여 사전에 더 큰 문자열을 찾을 수 있습니다. 그러나 그것보다 효율적인 방법은 여기서 정의 된 방법입니다.

이제 우리는 그들을 연결하거나 정렬 된 순서대로 인쇄해야합니다. 또한 사전 순으로 정렬 할 수 있도록 문자열 형식으로 입력을 가져와야합니다.

주어진 숫자를 배열하여 가장 큰 숫자를 만듭니다.

암호

주어진 숫자를 배열하여 가장 큰 숫자를 형성하는 C ++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int myCompare(string X, string Y)
{
    string XY = X.append(Y);
    string YX = Y.append(X);

    return XY.compare(YX) > 0 ? 1: 0;
}
void getLargest(vector<string> arr)
{
    sort(arr.begin(), arr.end(), myCompare);

    for (int i=0; i < arr.size() ; i++ )
        cout << arr[i];
}
int main()
{
    vector<string> arr;
    arr.push_back("34");
    arr.push_back("86");
    arr.push_back("87");
    arr.push_back("765");
    getLargest(arr);
    return 0;
}
878676534

주어진 숫자를 배열하여 가장 큰 숫자를 형성하는 Java 코드

import java.util.Collections;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Vector;

class rearrangNumericString
{
    public static void getLargest(Vector<String> arr)
    {

        Collections.sort(arr, new Comparator<String>()
        {
            @Override
            public int compare(String X, String Y)
            {

                String XY=X + Y;

                String YX=Y + X;

                return XY.compareTo(YX) > 0 ? -1:1;
            }
        });

        Iterator it = arr.iterator();

        while(it.hasNext())
            System.out.print(it.next());

    }
    public static void main (String[] args)
    {
        Vector<String> arr = new Vector<>();
        arr.add("34");
        arr.add("86");
        arr.add("87");
        arr.add("765");
        getLargest(arr);
    }
} 
878676534

복잡성 분석

시간 복잡성

O (N * | S | log N) 어디에 "엔" 숫자의 개수이고 | S | 가장 큰 숫자의 길이를 나타냅니다. 병합 정렬은 N logN 비교를 수행하지만 각 비교는 | S | 최악의 경우 시간. 시간 복잡성도 N * | S | logN.

공간 복잡성

O (N * | S |) 어디에 "엔" 숫자의 개수입니다. 여기 | S | 숫자 입력의 길이를 나타냅니다.

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