java - 检查数组中的数字是否在 0-array.length -1 之间

Question

我需要编写一个程序来检查数组内的所有数字是否在 0 到 array.length-1 之间，并且只出现一次，返回 true 或 false。

例如[0,1,3,2]将返回True，[4,3.0,1]和[0,1,2 ,2] 都将返回 False。

我试着写一下:

public static boolean isPermutation (int[] array) {
    boolean isPermutation =true ;
      for (int i = 0 ; i<array.length & isPermutation; i = i+1) {
          for (int j = 1 ; j<array.length & isPermutation; j = j+1) {
              if (array[i]==array[j]|(array[i]>=array.length)) {
                  isPermutation =false ;
              }
          }
      }
      return isPermutation ;
}

问题是，当我们检查 array[i]==array[j] 时，它等于 i 等于 j 而不是数组中的数字。

有人可以帮忙吗？

Answer 1

您可以避免 for 循环内的 for 循环，并可以利用数学优势，不断添加所有数字，最后检查实际总和是否等于预期总和，然后返回 true，否则返回 false。如果所有数字都在范围内并且恰好出现一次，那么它们的总和将等于所有数字1到N的总和。同时，在扫描数组中的数字时，如果遇到任何大于数组长度-1或更少的数字大于零，可以立即返回 false。

以下代码可能会有所帮助。

public static boolean areNumbersInclusive(int[] arr) {
    long sum = 0;

    for (int n : arr) {
        if (n > arr.length - 1 || n < 0) {
            return false;
        }
        sum += n;
    }

    long intendedSum = ((arr.length - 1) * arr.length) / 2; // sum from 1 to n is n*(n+1)/2

    return intendedSum == sum;
}

public static void main(String args[]) {
    int[] arr1 = {1,0,5,3,2,4};
    int[] arr2 = {1,0,3,4};
    int[] arr3 = {-1,0,3,2};
    int[] arr4 = {1,0,3,2};

    System.out.println(areNumbersInclusive(arr1));
    System.out.println(areNumbersInclusive(arr2));
    System.out.println(areNumbersInclusive(arr3));
    System.out.println(areNumbersInclusive(arr4));
}

这将按预期打印以下输出。

true
false
false
true

这是OP的正确版本的方法，尽管我的答案可以避免嵌套for循环。

public static boolean isPermutation(int[] array) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] >= array.length || array[i] < 0) {
            return false;
        }
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return false;
            }
        }
    }

    return true;
}