0 
public static boolean hasTwoPair(int[] arrayOfInts){    
}

int如果该方法可以找到两对不同的匹配值，则该方法应该返回 true 。所以如果数组是{2,2,4,7,7}，它应该返回真，因为它有两个 2 和两个 7。

它只适用于不同的对值。如果是{2,2,2,2,5}，它将返回 false ，因为它们不是不同的对值。

编辑：这是我到目前为止的方法主体：

     boolean pairFound = false;
    int pairValue;

    for(int s = 0; s < arrayOfInts.length - 1; s++){
        pairValue = arrayOfInts[s];

        for(int c = s + 1; c < arrayOfInts.length; c++){
            if(pairValue == arrayOfInts[c])
                pairFound = true;
        }
    }

    return false; //placeholder

我不知道从这里去哪里。

4

4 回答 4

2

此任务要求您构建计数列表：

  • 创建一个数据结构（例如 a Map<Integer,Integer>），其中包含数组中每个数字的计数。
  • 浏览地图，并计算计数为 2 及以上的条目数。
  • 如果您计算了两个或更多项目，则返回true；否则，返回false。

您的第一个示例的计数如下所示：

V   #
-   -
2 - 2
4 - 1
7 - 2

您有两个计数为 2 的项目（2 和 7），所以 return true。

您的第二个示例的计数如下所示：

V   #
-   -
2 - 4
5 - 1

只有一项的计数大于 2，所以 return false。

如果您使用 a HashMap，则此算法会在 中生成答案O(n)。

于 2013-11-15T02:50:24.317 回答
1

由于您实际上没有尝试过任何代码，因此我将描述如何解决此问题，但没有实际代码。

从初始化为的booleanlike开始，并在找到第一个. 此外，您需要一个(来跟踪找到的第一对的值（如果您找到了）。pairFoundfalsetruepairintpairValue

遍历，寻找一对。如果您找到一对，并且pairFound为假，则设置pairFound为true，并设置pairValue为您的第一个 found 的值pair。现在继续迭代。

如果你找到一对 and pairFoundistrue并且这个对 is != pairValue，那么return true;. 如果您遍历所有内容并且尚未返回true，那么您可以return false.

根据您更新的问题，您非常接近。

boolean pairFound = false;
int pairValue = Integer.MIN_VALUE;  
//or some value that arrayOfInts will never have based on context

for(int s = 0; s < arrayOfInts.length - 1; s++){
    if(arrayOfInts[s] == pairValue) { 
        continue; 
    }
    for(int c = s + 1; c < arrayOfInts.length; c++){
        if(arrayOfInts[s] == arrayOfInts[c]) {
            if(arrayOfInts[s] != pairValue) {
                if(pairFound) {    
                    return true;
                }
                pairValue = arrayOfInts[s];
                pairFound = true;
                break;
            }
        }
    }
}
return false;
于 2013-11-15T02:48:55.127 回答
0

您不需要对数组进行排序，这会产生 O(n*log(n)) 复杂性。但是您当前的解决方案更糟糕，因为它会产生 O(n^2) 复杂性。但是您也不需要 HashMap。一个 Set 和一个整数就足够了：

  • 对于每个数组元素
    • 检查：元素是否已经在集合中？
      • 如果不放入集合中
      • 如果是，请检查它是否等于您最后找到的 Int 对（是的，使用盒装的 Int，而不是这里的原始 int，以便能够用 初始化它null）
        • 如果相等继续
        • 如果不相等
          • 如果最后找到的对null设置为元素值
          • 否则你就完成了，你至少有 2 对不同的对
  • 如果您在未达到最后一个条件的情况下遍历列表，则您没有 2 个不同的对

至于 Set 实现，我会推荐一个HashSet

不过这里还有很多话要说。如果你像这样实现它，你就不会假设整数和可索引数组。您所需要的只是一个可比较元素的列表。因此，您可以使方法的签名更加通用：

public static boolean hasTwoPair(Iterable<E> iterable)

但是由于数组不支持泛型和 Iterable 接口，因此该方法的每个客户端都必须使用该方法将 Array 参数转换为 Iterable asList()。如果这太不方便，您可以提供另一种方法：

public static <T> boolean hasTwoPair(T[] array)

一般来说，在设计 API 时使用尽可能通用的类型是个好主意（另请参阅“Effective Java, Second Edition”中的条款 40 和 52）

于 2013-11-15T06:16:26.370 回答
0

对数组进行排序。然后查找匹配的前两个连续值。如果找到，跳到与匹配对不同的第一个条目并重复。如果在第一次或第二次搜索成功之前到达数组的末尾，则返回false。

于 2013-11-15T02:50:55.433 回答