搜索算法(优于线性算法)

Question

如果整数数组中存在三个3s (如果它们不是连续的)，我必须编写一个返回true的方法。我在这里编写了以下代码:但是，它正在返回true (它不应该这样做)。有人能指出我的错误吗？Arr[]={4，3，5，2，3，3}；

这也是一种线性算法。还能做得更好吗？

public static boolean consecutiveThree(int[] arr) {
        int x=0;
        for(int i=0;i<arr.length-1;i++) {

            if((arr[i]!=3 && arr[i+1]==3) || (arr[i]==3 && arr[i+1]!=3)) {
                x++;
                //continue;

            }

            if(x==3)
                return true;

        }
        return false;
    }

Answer 1

你说过：

如果整数数组中有三个3s，则返回(条件是它们是而不是连续的)

我的解释是至少有三个3s，没有两个3s是相邻的。

public static boolean hasThreeNonconsecutiveThrees(int... values) {
    int count = 0, streak = 0;
    for (int value : values) {
        if (value != 3)
            streak = 0;
        else if (++streak == 2)
            return false; // Found two consecutive (adjacent) 3s
        else
            count++;
    }
    return (count >= 3);
}

测试

    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,2,3,3)); // false
    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,3,2,3)); // true
    System.out.println(hasThreeNonconsecutiveThrees(1,2,3,4,3));   // false
    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,3,3,3)); // false

输出

false
true
false
false

Answer 2

在最坏的情况下，正确的数组将以... 3 3 X 3结尾。除非数组有些排序，或者有些特殊，否则您必须查看每个元素才能到达最后三个3s。如果数组是随机的，则需要线性复杂度，因为必须检查数组中的每个元素。

Answer 3

您的算法没有检查arr[i-1]是否是'3'。这是你算法的错误。

试试这个：-

public static boolean consecutiveThree(int[] arr) {
    int x = 0;
    for (int i = 0; i < arr.length; i++) {

        if (arr[i] == 3) {
            if (i == 0) { // zero 'th element do not have arr[i-1].
               if(arr[i + 1] != 3) {
                x++;
               }
            } else if (i == arr.length - 1) { // last element do not have arr[i+1].
               if((arr[i - 1] != 3)) {
                x++;
               }
            } else if ((arr[i + 1] != 3) && (arr[i - 1] != 3)) {
                x++;
            }
        }

        if (x == 3) // may be x >= 3
            return true;

    }
    return false;
}