配列Leetcodeソリューションのランク変換


難易度 簡単に
よく聞かれる Amazon (アマゾン) Facebook Google
配列

配列リートコードソリューションのランク変換の問題により、 配列 整数の。 配列または指定されたシーケンスはソートされていません。 指定されたシーケンスの各整数にランクを割り当てる必要があります。 ランクの割り当てにはいくつかの制限があります。

  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のXNUMXつのインスタンスが含まれます。

配列リートコードソリューションのランク変換のアプローチ

配列リートコードソリューションのランク変換の問題により、指定されたシーケンスにランクを割り当てるように求められました。 満たすべき条件は、問題の説明にすでに記載されています。 だから、もう一度説明する代わりに。 ソリューションを直接確認します。 したがって、例に見られるように。 ソートされたシーケンスにランクを割り当てる方が簡単です。 したがって、順序付けられたマップを使用して、指定された入力シーケンスの要素を格納します。 順序付けられたマップを使用すると、要素が並べ替えられた順序になっていることを確認できます。

ここで、1番目の条件に対処する必要があります。 1番目の条件は、可能な限り最小のランクを割り当てる必要があることを示しています。 したがって、マップ上に存在するキーにXNUMXからの番号を割り当てるだけです。 これにより、課せられたXNUMXつの条件すべてが処理されます。 数字が大きいほどランクが高くなります。 ランクはXNUMXから始まります。可能な限り小さいです。

ここで、入力シーケンスをトラバースして、マップに格納されているランクを割り当てるだけです。

コード

配列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)、 順序付けられたマップを使用したため、挿入、削除、および検索の対数係数があります。

スペースの複雑さ

オン)、 順序付けられたマップを使用して要素を入力に格納するためです。