배열 Leetcode 솔루션의 순위 변환

난이도 쉽게
자주 묻는 질문 아마존 Facebook 구글
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 30

배열 Leetcode 솔루션의 문제 순위 변환은 우리에게 정렬 정수 배열 또는 주어진 시퀀스가 ​​정렬되지 않았습니다. 주어진 시퀀스의 각 정수에 순위를 할당해야합니다. 순위 할당에는 몇 가지 제한 사항이 있습니다.

  1. 순위는 1로 시작해야합니다.
  2. 숫자가 클수록 순위가 높아집니다 (숫자 측면에서 더 커짐).
  3. 순위는 각 정수에 대해 가능한 한 작아야합니다.

배열 Leetcode 솔루션의 순위 변환

자, 몇 가지 예를 살펴 보겠습니다.

arr = [40,10,20,30]
[4,1,2,3]

설명 : 주어진 입력을 정렬하면 예제를 더 쉽게 이해할 수 있습니다. 정렬 후 입력은 [10, 20, 30, 40]이됩니다. 이제 주어진 규칙을 따른다면. 순위는 새로 수정 된 배열에 따라 [1, 2, 3, 4]가됩니다. 출력의 요소와 일치하는 경우. 그들은 동일하여 출력의 정확성을 확인합니다.

[100,100,100]
[1, 1, 1]

설명 : 입력의 모든 요소가 동일하기 때문입니다. 따라서 모두 1 인 동일한 순위를 가져야합니다. 따라서 출력에는 1의 세 인스턴스가 포함됩니다.

배열 Leetcode 솔루션의 순위 변환 방법

배열 Leetcode 솔루션의 순위 변환 문제는 주어진 시퀀스에 순위를 할당하도록 요청했습니다. 충족해야하는 조건은 문제 설명에 이미 명시되어 있습니다. 따라서 다시 한 번 설명하는 대신. 솔루션을 직접 살펴 보겠습니다. 따라서 예제에서 볼 수 있습니다. 정렬 된 시퀀스에 순위를 할당하는 것이 더 쉽습니다. 따라서 우리는 주어진 입력 시퀀스에 요소를 저장하기 위해 정렬 된 맵을 사용합니다. 정렬 된 맵을 사용하면 요소가 정렬 된 순서로되어 있는지 확인합니다.

이제 우리는 세 번째 조건을 다루어야합니다. 세 번째 조건은 가능한 한 가장 작은 순위를 할당해야한다는 것입니다. 따라서지도에있는 키에 1부터 숫자를 할당하기 만하면됩니다. 이것은 세 가지 부과 된 조건을 모두 처리합니다. 더 큰 숫자의 순위가 더 높습니다. 순위는 1부터 시작합니다. 가능한 한 작습니다.

이제 입력 시퀀스를 탐색하고 맵에 저장된 순위를 할당합니다.

암호

배열 Leetcode 솔루션의 순위 변환을위한 C ++ 코드

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

vector<int> arrayRankTransform(vector<int>& arr) {
    map<int, int> m;
    for(auto x: arr)
        m[x] = 1;
    int lst = 0;
    for(auto x: m){
        m[x.first] = lst + 1;
        lst++;
    }
    for(int i=0;i<arr.size();i++)
        arr[i] = m[arr[i]];
    return arr;
}

int main(){
    vector<int> input = {40, 10, 30, 20};
    vector<int> output = arrayRankTransform(input);
    for(auto x: input)
        cout<<x<<" ";
}
4 1 3 2

어레이 Leetcode 솔루션의 Java 코드 순위 변환

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int[] arrayRankTransform(int[] arr) {
        Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
        for(int x: arr)
            m.put(x, 1);
        int lst = 0;
        for(Integer x: m.keySet()){
            m.put(x, lst + m.get(x));
            lst = m.get(x);
        }
        for(int i=0;i<arr.length;i++)
            arr[i] = m.get(arr[i]);
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] input = {40, 10, 30, 20};
    int[] output = arrayRankTransform(input);
    for(int x: output)
      System.out.print(x+" ");
  }
}
4 1 3 2

복잡성 분석

시간 복잡성

O (NlogN), 정렬 된 맵을 사용했기 때문에 삽입, 삭제 및 검색을위한 로그 계수가 있습니다.

공간 복잡성

의 위에), 입력에 요소를 저장하기 위해 정렬 된 맵을 사용하기 때문입니다.

코멘트를 남겨

Translate »
1