检查数组中0-array.length-1之间的数字

Question

我需要编写一个程序来检查数组中的所有数字是否介于0到数组之间。长度为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 ;
}

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

有人能帮忙吗？

Answer 1

通过使用集合，可以轻松检查数组中是否有相同的数字，因为集合只存储每个数字的一次出现，然后在一个循环中检查所有数字是否在0范围内。。大堆长度-1：

public static boolean isPermutation (Integer[] array) {
    int length = array.length;

    Set<Integer> set = new HashSet<Integer>(Arrays.asList(array));
    if (set.size() < length)
        return false;

    for (int x : array) {
        if ((x < 0) || (x > length - 1))
            return false;
    }

    return true;
}

public static void main(String[] args) {
    Integer[] a = {0, 1, 3, 2};
    Integer[] b = {0, 1, 3, 1};
    Integer[] c = {0, 1, 3, -1};

    System.out.println(isPermutation(a));
    System.out.println(isPermutation(b));
    System.out.println(isPermutation(c));
}

将打印：

true
false
false

或者更好地避免循环，方法是仅使用有效值将集合过滤到列表，并检查列表大小是否等于数组长度：

public static boolean isPermutation (Integer[] array) {
    int length = array.length;
    Set<Integer> set = new HashSet<Integer>(Arrays.asList(array));
    if (set.size() < length)
        return false;
    List<Integer> list = set.stream().filter(x -> x >= 0 && x < length).collect(Collectors.toList());
    return list.size() == length;
}

Answer 2

您可以在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;
}