0

我试图在两个数组中找到相同的元素，其中元素之间的最大距离必须等于 k。

我的两个数组（大小不同且未排序）A 和 B，k 最大距离。

这就是我所做的，但我不知道哪里有错误......

for (int i = 0; i<A.length; i++){
    for(int j = i; j < k || j < B.length; j++)
        if(A[i] == B[j]){
            //Print on console
            System.out.println(B[i]);
            j = k;
        }
    }
}

例如：

A[3,7,5,9,10,15,16,1,6,2] 
B[4,8,5,13,1,17,2,11] 
k=6

输出应该是5 1 2，但我不知道为什么，我的程序只给我5。谁能帮我理解为什么？

4

7 回答 7

1 
for (int i = 0; i < A.length; i++) {
    int startIndex = Math.max(i - k + 1, 0);
    int endIndex = Math.min(i + k, B.length);
    for (int j = startIndex; j < endIndex; j++){
        if (A[i] == B[j]) {
            System.out.println(B[j]);
        }
    }
}

呃，哦，不知道你到底想要多少距离，包括当前元素还是排除它。此外，重复（在同一范围内）可能是要处理的特殊情况。

于 2013-08-19T11:44:22.793 回答
0

尝试这个：

for (int i = 0; i<A.length; i++){
            for(int j = 0; j < B.length; j++)
                if(A[i] == B[j] && Math.abs(j-i)<k){
                    //Print on console
                    System.out.println(B[j]);
                }
            }
于 2013-08-19T11:28:46.563 回答
0

好吧，您从 i 开始 j，因此它将仅迭代 B 中位于 A 的 i 元素之后的项目。

这可能有效

    for (int i = 0; i<A.length; i++){
        for(int j =Math.max(0, i-k) ; j < Math.min(B.length, i+k); j++){
            if(A[i] == B[j]){
                System.out.println(B[j]);
            }
        }
    }

或者：

    for (int i = 0; i<A.length; i++){
        for(int j = 0; j < B.lenght; j++){
            if(A[i] == B[j] && Math.abs(i-j)<=k){
                System.out.println(B[j]);
            }
        }
    }
于 2013-08-19T11:25:13.843 回答
0

嗯，你有一种奇怪的风格来做到这一点。你为什么这样做j = i？如果这样做，则不会遍历所有值。

这可能会帮助你。我试了一下它应该可以工作：

    int[] a = {3,7,5,9,10,15,16,1,6,2};
    int[] b = {4,8,5,13,1,17,2,11};

    int k = 6;

    for (int i = 0; i < b.length; i++) {
        for (int j = 0; j < k || j < a.length; j++) {
            if (b[i] == a[j]) {
                System.out.println(a[j]);
            }
        }
    }
于 2013-08-19T11:17:50.060 回答
0

这是解决方案。我检查了，它有效。

你的错误

  • 您的第二个循环初始化和停止条件是错误的。它应该从 i - k 开始（如果它小于 0，那么它应该从 0 开始）并在 j 超过 i + k 时停止。第二个循环应该在数组边界中的 i - k 和 i + k 之间运行。
  • 您无条件地将第二个循环变量设置为 k ，这会导致意外行为。循环可能会返回一个旧值，导致无限循环。
  • 您控制 B[j] 值，但打印 B[i] 值。这可能会导致数组越界异常。

int[] a = { 3, 7, 5, 9, 10, 15, 16, 1, 6, 2 }; int[] b = { 4, 8, 5, 13, 1, 17, 2, 11 }; 诠释 k = 6;

    for (int i = 0; i < a.length; i++) {
        for (int j = ((i - k) < 0 ? 0 : i - k); j < i + k && j < b.length; j++) {

        if (a[i] == b[j]) {
            System.out.println(b[j]);
        }
    }  

    }
于 2013-08-19T11:35:23.960 回答
0

我不明白k应该做什么，但你的方法是O(n^2)，这太过分了。

使用集合，您可以很容易地找到交叉点：

Set<Integer> aSet = new HashSet<Integer>();
// Adding an element to a set is O(1), this addAll operation is therefore O(n)
Collections.addAll(aSet, A);

// This loop is also O(n), as contains is O(1)
for (int b : B) {
    if (aSet.contains(b)) {
        // this b int is in A and b
    }
}

总的来说，这种方法是O(n)

编辑

至于k，我对你在做什么的理解是你只是在测试那个j < k，这解释了为什么只有 5 个出来。您需要测试 i 和 j 之间的距离，该距离由

Math.abs(j-i) < k
于 2013-08-19T12:03:49.497 回答
0 
def getSameItems(aList, bList):
    a_max = aList[0]
    b_max = bList[0]
    for item in aList:
        if item > a_max: a_max = item
    for item in bList:
        if item > b_max: b_max = item
    aList_counting = [0] * (a_max + 1)
    bList_counting = [0] * (b_max + 1)

    for item in aList: aList_counting[item] += 1
    for item in bList: bList_counting[item] += 1
    min_item = a_max if a_max < b_max else b_max
    sameList = []
    for i in range(min_item + 1):
        if aList_counting[i] > 0 and bList_counting[i] > 0:
            sameList.append(i)
    return sameList
aList = [1, 7, 2, 2, 8]
bList = [1, 2, 3, 7, 7, 9, 2, 8]
print getSameItems(aList, bList)
[1, 2, 7, 8]

以上代码使用的是python语言，本人是中国人，所以英文不好，无法提供丰富的代码注释，sorry..建议大家可以使用计数排序的思路，希望对您有所帮助！

于 2017-12-08T03:52:16.990 回答