2 つの和 X=x1+x2+...+xn と Y=y1+y2+...+ym を考えてみましょう。xi を yj と交換すると 2 つの和が等しくなるようなインデックス i と j を見つけるアルゴリズムを与えてください。つまり、X-xi+yj = Y-yj+xi が存在する場合です。
こんにちは、みんな！そこに説明が表示されます。最初に、2 つのソートされていない配列を取得しています。それから私はそれらを並べ替えます。次に、それらの違いを見つけるためにそれらを互いに減算する必要があり、次に2つのforループで配列の要素の違いを比較します。
ここに私のコードがあります
Timport java.util.ArrayList;
public class algorithm {
int j;
int i;
int key;
public algorithm() {
super();
// TODO Auto-generated constructor stub
}
public ArrayList<Integer> sortingFunction(ArrayList<Integer> array){
for(j=1;j<array.size();j++){
key = array.get(j);
i = j - 1;
while (i>=0 && array.get(i)>key){
array.set(i+1, array.get(i));
i = i - 1;
}
array.set(i+1, key);
}
return array;
}
public int calculationFunction(ArrayList<Integer> array){
int sum = 0;
for(int x = 0; x<array.size(); x++){
sum += array.get(x);
}
return sum;
}
public void writingFunction(ArrayList<Integer> array){
for(int x = 0; x<array.size(); x++){
System.out.print(array.get(x)+" ");
}
System.out.println();
}
public void twoSumsEqualAlgorithm (int x, int y, ArrayList<Integer> array1, ArrayList<Integer> array2 ){
int x_copy = x;
int y_copy = y;
//System.out.println(x);
//System.out.println(y);
for(int i = 0; i<array2.size(); i++){
x_copy = x + (array2.get(i) * 2);
//System.out.print("x;"+ x_copy);
//System.out.println(" y;"+ y);
if(x_copy >= y){
for(int j = 0; j<array1.size(); j++){
y_copy = y + (array1.get(j) * 2);
if(x_copy == y_copy){
System.out.print("we have found the true values; ");
System.out.print("'"+array1.get(j)+"'"+" from myArray1("+j+ ") and ");
System.out.println("'"+array2.get(i)+"'"+" from myArray2("+i+")");
//return;
}
else if(x_copy < y_copy){
//System.out.println("x is lower than y");
break;
}
}
}
}
}
private void exit(int k) {
// TODO Auto-generated method stub
}
}
これがテスト部分です
import java.util.ArrayList;
public class test {
/**
* @param args
*/
public static void main(String[] args) {
ArrayList<Integer> myArr1 = new ArrayList<Integer>();
ArrayList<Integer> myArr2 = new ArrayList<Integer>();
algorithm alg = new algorithm();
myArr1.add(8);
myArr1.add(4);
myArr1.add(2);
myArr1.add(15);
myArr1.add(10);
myArr1.add(16);
myArr1.add(1);
myArr1.add(11);
myArr2.add(5);
myArr2.add(3);
myArr2.add(7);
myArr2.add(6);
myArr2.add(19);
myArr2.add(2);
myArr2.add(12);
myArr2.add(1);
myArr2.add(0);
myArr1 = alg.sortingFunction(myArr1);
myArr2 = alg.sortingFunction(myArr2);
System.out.print("myArray1; ");
alg.writingFunction(myArr1);
System.out.print("myArray2; ");
alg.writingFunction(myArr2);
System.out.print("sum of myarray1; ");
System.out.println(alg.calculationFunction(myArr1));
System.out.print("sum of myarray2; ");
System.out.println(alg.calculationFunction(myArr2));
alg.twoSumsEqualAlgorithm(alg.calculationFunction(myArr1), alg.calculationFunction(myArr2), myArr1, myArr2);
}
}
したがって、アルゴリズムの複雑さを計算すると、O(n^2) になると思います。いくつかの投稿を読んだところ、O(nlgn) の複雑さで同じ仕事ができると書かれています。
2 つの配列リストを比較すると、big-O が低くなる方法で行うことができます。
マージソートまたはクイックソート O(nlg(n)) を使用して各配列リストをソートし、O(n) でソートされた 2 つのリストを比較できます。結果は O(nlgn) です。
しかし、別のアルゴリズム (並べ替えなし) は、1 つの配列 (n) 内の各要素を反復処理します。そして、要素が別の配列 (n) であるかどうかをチェックします (そして、重複を適切に処理するためにマークします)。この後者のアルゴリズムは O(n^2) です。
そのため、実装する方法がありませんでした。何か案は？