リスト操作アルゴリズムが遅すぎる

Question

n個の整数a1、a2、...、anのシーケンスがあります。シーケンス内のすべての要素を最小要素で変更する必要があります。最小要素はその前に配置されます。そのような要素がない場合は、-1に置き換える必要があります。すべての変更は、同時かつ独立しています。

例：

4 3 1 2 1 - > -1 4 3 3 2

5 4 3 2 1 - > -1 5 4 3 2

マイコードが遅すぎるとシーケンスが大きすぎるとタイムアウトエラーのテストに合格しません。どのように性能を向上させることができますか？

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    for (int i = 0; i < list.size(); i++) { 
     int tmp = -1; 
     for (int j = i - 1; j >= 0; j--) { 
      if (list.get(i) < list.get(j)) { 
       if (list.get(j) < tmp || tmp == -1) { 
        tmp = list.get(j); 
       } 
      } 
     } 
     newList.add(tmp); 
    } 
    list = newList; 
} 

UPDATE：

は、ここに私のコードである私は、新しい値は、我々は変更の要素よりも大きくなければならないことを言及するのを忘れてしまいました。

Answer 1

ありがとう！木のセットと天井の方法はそれを働かせた：

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    TreeSet<Integer> set = new TreeSet<>(); 
    for (Integer aList : list) { 
     Integer tmp = set.ceiling(aList + 1); 
     if (tmp == null) { 
      newList.add(-1); 
     } else { 
      newList.add(tmp); 
     } 
     set.add(aList); 
    } 
    list = newList; 
} 

ありがとうございました！

Answer 2

public static void main(String[] args) { 
    int[] values = {10,3,5,7,9,2,2,14,-5,7,9,3}; 

    if (values.length == 0) { return; } 

    int minValue = values[0]; 
    int temp; 
    values[0] = -1; 

    for(int i=1; i<values.length; i++) { 
     temp = values[i]; 
     values[i] = minValue; 
     if (temp < minValue) { 
      minValue = temp; 
     } 
    } 

} 

現在のアイテムまでの最小値を覚えておいて、新しいアイテムを見つけたら交換してください。これはO（N）で実行されており、追加のメモリは必要ありません。

Answer 3

現在ネストされたループの構築方法のため、あなたのアプローチは時間的にO（n^2）です（nはリストのサイズです）。

内部ループは必要ありません。リストに追加する次の値、つまり新しいリストの前の値にすでに上限があります。次の要素は、入力リスト内の対応する先行要素が小さい場合にのみ小さくなります。だからちょうどそれらの2つの数字の小さい方を取る。 CPPの初心者のアドバイスに

List<Integer> newList = new ArrayList<>(); 
if (list.size() > 0) { newList.add(-1); } 
if (list.size() > 1) { newList.add(list.get(0)); } 
for (int i = 2; i < list.size(); i++) { 
    newList.add(Math.min(list.get(i-1), newList.get(i-1))); 
}