0

考虑两个和，X=x1+x2+...+xn，并且 Y=y1+y2+...+ym。给出一个找到索引 i 和 j 的算法，使得交换 xi 和 yj 使两个和相等，即 X-xi+yj = Y-yj+xi ，如果它们存在的话。

嗨，大家好！所以在那里你可以看到描述。所以首先我得到两个未排序的数组。然后我对它们进行排序。然后我必须将它们彼此相减才能找到它们之间的差异，然后在两个 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) 复杂度做同样的工作。

比较两个数组列表的方式可以导致 a 较低的 big-O 但使用 >sorting。

您可以使用合并排序或快速排序 O(nlg(n)) 对每个数组列表进行排序，然后在 O(n) 中比较两个 > 排序列表。结果是 O(nlgn)。

但是另一种算法（没有排序）将遍历一个数组（n）中的每个元素。然后 >then 检查该元素是否是另一个数组 (n)（并标记它以正确处理重复项）。后一种算法是 O(n^2)。

比较两个排序的 int 数组

所以我只是无法实施。有任何想法吗？

4

2 回答 2

1

所以你需要解决 xi-yj == (XY)/2

对 y 数组进行排序并在 x 数组上循环。对于每个 x_i，在 y 数组中对 (XY)/2-xi 进行二分搜索。如果你发现什么停止，否则继续。排序的复杂度为 O(n log n)。每次查找的复杂度为 O(log n)，您最多需要 n 次查找 --> 总复杂度为 O(n log n)

于 2013-03-13T21:22:22.853 回答
0

你想要做的不是两个数组的比较。它的设计相似，但我会像这样解决一个完全不同的任务：

1）合并排序或快速排序两个集合。如果设计得当，这是 O(nlgn)。

2) 将集合 x 和集合 y 中的数字相加，计算 XY 为差 D.O(n)。

3) （假设 D 为负）对 x 从小到大进行扫描，对 y 从大到小进行扫描。对于 x 扫描中的每个元素，检查 y 扫描中的每个元素，直到交换 x 和 y 会使 D 过去为零。如果发生这种情况，推进 x 并继续检查 y 扫描中的元素（例如，不要在每次推进 x 扫描时重置 y 扫描）。

如果你让 D 准确地达到零，那么你已经找到了你的交换。这是最坏的 O(n)，因为您只读取 x 的元素一次，并且最多读取 y 的元素 x.length+y.length 次。

4）（假设 D 为正）执行与上述类似的逻辑，但从最大到最小扫描 x，从最小到最大扫描 y。

于 2013-03-13T21:24:50.333 回答