1組の数に複数の数の和が存在するかどうかは既知数に等しい
1172 ワード
1.2つの数の和が既知数(key)と等しいかどうか.
A:窮挙:配列中に2つの数を選択する、既知数、複雑度O(N^2)に等しいか否かを判断する.
B:二分:まず並べ替え(秩序がある場合は不要)、次に二分してM-array[i]がこの配列に存在するかどうかを調べ、複雑度O(N*log(N)).
C:まず並べ替え(秩序がある場合は不要)、次に2つのポインタ(ヘッドポインタheadとテールポインタtail)を用いて、*head+*tail>keyの場合、tail--、小さい場合はhead++であり、等しい場合は存在する.
Cの場合:
練習:SOJ SUM http://cs.scu.edu.cn/soj/problem.action?id=1627
A:窮挙:配列中に2つの数を選択する、既知数、複雑度O(N^2)に等しいか否かを判断する.
B:二分:まず並べ替え(秩序がある場合は不要)、次に二分してM-array[i]がこの配列に存在するかどうかを調べ、複雑度O(N*log(N)).
C:まず並べ替え(秩序がある場合は不要)、次に2つのポインタ(ヘッドポインタheadとテールポインタtail)を用いて、*head+*tail>keyの場合、tail--、小さい場合はhead++であり、等しい場合は存在する.
Cの場合:
int getResult(int *num, int n_len, int key, int &num_1, int &num_2) {
int *i, *j;
int temp;
i = num, j = num + n_len - 1;
while (i < j) {
temp = *i + *j;
if (temp > key) {
j--;
} else if (temp < key) {
i++;
} else {
num_1 = *i;
num_2 = *j;
return true;
}
}
return false;
}
public static void getResult(int[] num_Array, int len, int key) {
int i, j, temp;
i = 0;
j = len - 1;
while (i < j) {
temp = num_Array[i] + num_Array[j];
if (temp > key) {
j--;
} else if (temp < key) {
i++;
} else {
System.out.println(num_Array[i] + " " + num_Array[j]);
return;
}
}
}
練習:SOJ SUM http://cs.scu.edu.cn/soj/problem.action?id=1627