O（N）時間とO（C）空間の複雑さでJava 8ストリームAPIを使用してリストからmax（min）を1つだけ削除する方法

Question

ここでは最大値の1つだけを削除するコードです最初のものですが、これは無関係です）。時間的にはO(n)であり、入力の範囲を超えているのはO(n)です。

public List<Integer> removeOneOfTheMax(List<Integer> nums) { 
    int max = Integer.MIN_VALUE; 
    int maxIndex = -1; 
    Iterator<Integer> it = nums.iterator(); 
    for (int i = 0; it.hasNext(); i++) { 
     Integer temp = it.next(); 
     if (max < temp) { 
      maxIndex = i; 
      max = temp; 
     } 

    } 
    nums.remove(maxIndex); 
    return nums; 
} 

1.

は何のJava 8ストリームAPIを用いた方法と同等のでしょうか？私は時間と空間の複雑さを保ちたいので、並べ替えはできません。あなたは上記のコードに LinkedListを渡す場合

2.実際には、スペースの複雑さは、（入力を越えて再び、）O(C)だろうが、私の知る限り理解し.stream()は、追加のデータ構造にそのストリームAPIを作成しますスペースは少なくともO(N)でなければなりません。私が間違っているなら、私を訂正してください。

Answer 1

ストリームソリューションは次のようになります。

int maxIndex = IntStream.range(1, nums.size()).reduce(0, (i, j) -> { 
     int left = nums.get(i); 
     int right = nums.get(j); 
     return Integer.max(left, right) == left ? i : j; 
    }); 

    nums.remove(maxIndex); 

は、その下Spliterratorがあるように起こっています。

ストリーム操作自体は、追加のデータ構造を作成しません。