同じ値の要素を 3 つ以上含まない整数配列 d があります。異なる昇順のトリプル (d[i] < d[j] < d[k]、i < j < k) はいくつ存在しますか?
入力形式:
最初の行には、配列の要素数を示す整数 N が含まれています。この後に、先頭/末尾のスペースなしで単一のスペースで区切られた N 個の整数を含む単一の行が続きます
出力フォーマット：
配列内に存在する個別の昇順トリプルの数を示す単一の整数
制約:
N <= 10^5 配列内のすべての値は最大 2 回存在します 配列内のすべての値は 32 ビットの正の整数です
サンプル入力:
6 1 1 2 2 3 4
出力例:
4
説明：
明確なトリプレットは
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
別のテスト ケース:
入力：
10 1 1 5 4 3 6 6 5 9 10
出力：
28
DPを使用して解決しようとしました。しかし、15 のテスト ケースのうち、合格したのは 7 つのテスト ケースだけでした。この問題の解決を手伝ってください。
中間点として機能するトリプルの数を知るには、特定の要素よりも小さい/大きい要素の数だけを知る必要があることに注意してください。これを使用すると、トリプルの数を非常に簡単に計算できます。残っている唯一の問題は、重複を取り除くことですが、同じ要素が最大 2 つに制限されていることを考えると、これは些細なことです。
Binary Index Tree http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTreesを使用して解決しました。
http://www.kesannmcclean.com/?p=223という小さな記事も書きました。
私が思いついた暫定的なアルゴリズムの場合、次のようになります。
(K-1)!^2
ここで、K は一意の要素の数です。
編集
これについてさらに考えた後：
SUM[i=1,K-2] SUM[j=i+1,K-1] SUM[m=j+1,K] 1
=> SUM[i=1,K-2] (SUM[j=i+1,K-1] (K-j))
Pythonでの解決策の1つ:
from itertools import combinations as comb
def triplet(lis):
done = dict()
result = set()
for ind, num in enumerate(lis):
if num not in done:
index = ind+1
for elm in comb(lis[index:], 2):
s,t = elm[0], elm[1]
if (num < s < t):
done.setdefault(num, None)
fin = (num,s,t)
if fin not in result:
result.add(fin)
return len(result)
test = int(raw_input())
lis = [int(_) for _ in raw_input().split()]
print triplet(lis)
@hadron: 正確には、7 つの異なる数値のセットに対して35ではなく28にする必要がある理由を理解できました *
[クエリはトリプレットの昇順に関するものであるため、繰り返される数字は破棄できます]。
ところで、これは非常に悪い Java ソリューションです (N^3):
可能なトリプレットも出力しました。
また、入力「N」で可能なトリプレットの数を決定する関数についても考えています。
9 84
パッケージorg.HackerRank.AlgoChallenges;
import java.util.Iterator; java.util.Scanner をインポートします。java.util.TreeSet をインポートします。
パブリック クラス トリプレット {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int result = 0;
int n = scanner.nextInt();
Object[] array = new Object[n];
TreeSet<Integer> treeSet = new TreeSet<Integer>();
/*
* for (int i = 0; i < n; i++) { array[i] = scanner.nextInt(); }
*/
while (n>0) {
treeSet.add(scanner.nextInt());
n--;
}
scanner.close();
Iterator<Integer> iterator = treeSet.iterator();
int i =0;
while (iterator.hasNext()) {
//System.out.println("TreeSet["+i+"] : "+iterator.next());
array[i] = iterator.next();
//System.out.println("Array["+i+"] : "+array[i]);
i++;
}
for (int j = 0; j < (array.length-2); j++) {
for (int j2 = (j+1); j2 < array.length-1; j2++) {
for (int k = (j2+1); k < array.length; k++) {
if(array[j]!=null && array[j2]!=null && array[k]!=null){
System.out.println("{ "+array[j]+", "+array[j2]+", "+array[k]+" }");
result++;
}
}
}
}
System.out.println(result);
}
複雑さが気になりますか？
入力配列はソートされていますか?
複雑さを気にしなければ、N^3 の複雑さで解くことができます。
複雑度 N^3 のソリューション: 並べ替えられていない場合は、配列を並べ替えます。3 つの for ループを相互に使用し、配列を数値ごとに 3 回スローします。ハッシュ マップを使用して、すべてのトリプルをカウントします。キーはトリプル自体になり、値は出現回数になります。
次のようになります。
for (i1=0; i1<N; i1++) {
for (i2=i1; i2<N; i2++) {
for (i3=i2; i3<N; i3++) {
if (N[i1] < N[i2] < N[i3]) {
/* if the triple exists in the hash then
add 1 to its value
else
put new triple to the hash with
value 1
*/
}
}
}
}
結果 = ハッシュ内のトリプルの数。
私はそれを試していませんが、うまくいくはずだと思います。