一番小さいものは欲しくない、二番目に小さいものが欲しい
特定のオープンソースのオンライン学習プラットフォームの評価システムとの私の闘いに触発されました：
組み込み関数のセットが限られているコンピューター言語で作業しています。あなたはのセットを持っています$m$ 実数 $x_1, x_2, \dots x_m$。これらの数値は、任意の未知の順序です（つまり、必ずしも単調に増加または減少するとは限りません）。
これらの数値の「2番目に小さい」を返す関数を作成するとします。この場合、重複するエントリは別個のものとして扱われます。つまり、番号を小さいものから大きいものへとリストすると、この関数はその順序付きリストの2番目の番号を返します。たとえば、数字が$\{ 2, 6, 1, 7\}$、関数は $2$。数字が$\{ 4, 5, 4, 4, 4, 5 \}$、関数は $4$。
使用できる機能は次のとおりです。
max(x1, x2, ...)およびmin(x1, x2, ...)：任意の数の実数引数を受け入れます。それぞれ最大のものまたは最小のものを返します。sum(x1, x2, ...)：任意の数の実数引数を受け入れます。それらすべての合計を返します。
また、あなたは標準の算術演算を使用することができ+、-、*、/、と^。
ボーナス質問：
メソッドを拡張して、 $n$セットの中で最小の数。
両方の質問のための私の意図した答えはのみ使用max、sumおよび算術演算。ただし、このリストにある他の組み込み関数を使用したよりエレガントな答えを思い付くことができれば、それも私にとって興味深いことです。:-)
回答
私が思いつくことができる最高のものはこれです：
$$min((x_1+x_2),(x_1+x_3),\cdots,(x_{m-1}+x_m)) - min(x_1,x_2,\cdots,x_m)$$
すなわち
2つの数値の最小合計を見つけて、最小の数値で減算します。
だからのために $n$-番目に小さい：
の最小合計を見つけてみてください $n$ 数、そしてそれを最小の合計で引く $n-1$ 数字。
多分私はそれを取得しません（つまり、それは解決策であり、それが許可されているかどうかはわかりません）が、：
$max(min(set_1)min(set_2)…min(set_m))$ ここでそれぞれ $set_k$ を除くすべての番号が含まれます $x_k$ （そしてセットの数は等しい $(m)$ ）
とのために $3$rd最小数それは似ているでしょう
各「セット」には、2つを除くすべての数字が含まれ、そのすべての組み合わせが含まれるため、セットの数は次のようになります。 $(m)$バツ$(m-1)/2$。
とのために $4$最小の数は似ています
各「セット」には、3つを除くすべての数字が含まれ、そのすべての組み合わせが含まれるため、セットの数は次のようになります。 $(m)$バツ$(m-1)$バツ$(m-2)/(3!)$。
3で割った！私は特定の組み合わせを1つだけ取るので$x_i$、 $x_j$、 $x_k$、および無視（$x_j$、 $x_i$、 $x_k$）、（$x_k$、 $x_i$、 $x_j$）、（$x_j$、 $x_k$、 $x_i$）、（$x_k$、 $x_j$、 $x_i$）、（$x_i$、 $x_k$、 $x_j$）。
等々
このソリューションは、もともとathinのソリューションに触発されましたが、2つの最小数の合計を生成する方法が改善されています。コメントで示唆されているように、合計を最大に変更でき、最後に最小数を引く必要がないため、これはBassのソリューションの変形です。
入力に次のようにインデックスを付けましょう $x_0, x_1, \dots, x_{m-1}$。数字を書いてください$0, 1, \dots, m-1$バイナリで。それぞれについて$k=1,2,\dots,\lceil\log_2 m\rceil$、 $A_k$ すべての最小である $x_i$ そのような $i$ があります $0$ の中に $k$-番目の位置; しましょう$B_k$ すべての最小である $x_i$ そのような $i$ があります $1$ の中に $k$-番目の位置。次に、私たちの解決策は$$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ の数 $x$この式のは $m \lceil \log_2 m \rceil$。
これが機能する理由は次のとおりです。
各 $\max(A_k,B_k)$2つの要素の最大値になるため、少なくとも2番目に小さい要素になります。一方、$x_i$ そして $x_j$ 最小の2つです $x$の場合、何らかの位置が必要です $k$ ここで、のバイナリ表現は $i$ そして $j$異なる; いう、$i$ があります $0$ の中に $k$-番目の位置、および $j$ があります $1$。次に、$A_k = x_i$ そして $B_k = x_j$、 そう $\max(A_k,B_k) = \max(x_i,x_j)$私たちが取る分に間違いなく現れるでしょう。他にない$\max(A_{k'}, B_{k'})$ 小さくすることができるので $\max(x_i,x_j)$2番目に小さい要素である、が最終的な答えです。
完成した数式の例を次に示します。 $m=8$：
$$\min\Big(\max(\min(x_0,x_2,x_4,x_6),\min(x_1,x_3,x_5,x_7)), \max(\min(x_0,x_1,x_4,x_5),\min(x_2,x_3,x_6,x_7)), \max(\min(x_0,x_1,x_2,x_3),\min(x_4,x_5,x_6,x_7))\Big).$$
そして、これがhumnによって描かれたそのソリューションの図です：
これを一般化して $O(m \log m)$ を見つけるためのソリューション $k^{\text{th}}$賢くてハンサムな個人によって1年前に書かれたMath.SEの答えに頼ることによる最小の要素。
これはランダムな構造にすぎないので、私は「一種の」と言います。一部のランダム入力でのみ機能するという意味ではありません。メソッドにある程度のランダム性がある式を生成する方法を説明するという意味で、ランダムです。正の確率で、すべての入力に対して常に機能する式が得られます。
方法は次のとおりです。
式の「句」は次のようになります。分割します$\{1,2,\dots,m\}$ に $k$ セット $S_1, S_2, \dots, S_k$、そして取る $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ これが生成する値は常に最大 $k$異なる要素、それはだ、少なくとも$k^{\text{th}}$最小。そして、$k$ 最小の要素はたまたまの間で均等に分散されています $S_1, \dots, S_k$、then節の値であります$k^{\text{th}}$ 最小の要素。
これが常に発生するようにするために、ランダムに多くの句を生成します。 $i \in \{1,2,\dots,m\}$、（独立して均一にランダムに）選択して、次のいずれかに配置します。 $S_1, \dots, S_k$。私がリンクしたMath.SEの回答に示されているように、$\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$条項の場合、正の確率で、 $k$変数には、それらを区切る句があります。これが発生した場合、最終的な式はこれらすべての句の最小値になります。
これがさらに別のアプローチです。@athinのメソッドと@JanIvanのメソッドの間にあるようなものです。
これは、2番目に小さい数が
他の数値よりも大きい（または等しい）最小の数値。
これは私たちができることを意味します
可能なすべてのペアワイズmax（）に対するmin（）： $$\min\left(\max(x_1, x_2), \max(x_1,x_3),\ldots, \max(x_{m-1}, x_m)\right)$$
これが機能することを再確認するには、次のことに注意するだけです。
最小数が同点でない限り、最小数がmax（）の1つとして表示されることはありません。これは、表示したい場合の特殊なケースです。