主页 / 问题 / 879021
Accepted
Roman C
Asked:2020-09-09 02:38:12 +0800 CST2020-09-09 02:38:12 +0800 CST

判断一个数组是否包含从 1 到 K 的整数

  • 772

编写一个函数，将一个由整数（按非递减顺序排序）和一个整数A组成的非空数组作为参数，检查 A 是否至少包含一次数字（从到的每个数字），并且不包含其他数字。例如，使用以下值：NK1,2, ..., K1K

int[] A = {1,1,2,3,3};
int K = 3;

该函数应该返回true。如果你问

int[] A = {1, 1, 3};
int K = 2;

或者

int[] A = {1, 1, 2, 3};
int K = 2;

该函数应该返回false。

我尝试编写以下函数，但无法正常工作

public boolean function(int[] A, int K){
  int n = A.length;
  for (int i = 0; i < n-1; i++){
    if (A[i+1] >= A[i]+1)
      return true;
    if (A[0] != 1 && A[i] != K)
      return false;
    else
      return true;
  }
  return true;
}

有什么问题？如果有人在代码中发现错误，非常感谢大家。

PS：我忘了补充一点，复杂性应该不会差O(n)。

java

4 个回答

  1. Best Answer

    由于数组已排序，因此执行以下操作就足够了：

    1) 检查第一个元素是否等于 1
    2) 检查最后一个元素是否等于 K
    3) 从第二个元素循环到最后一个元素，检查与前一个元素的差不超过 1

    因此，您的解决方案实际上是正确的，唯一的错误是循环内的条件，并且在出现乱序的情况下返回 true 而不是 false。

    public boolean function(int[] A, int K){
  int n = A.length;
  if (A[0] != 1)
      return false;
  if (A[n-1] != K)
      return false;
  for (int i = 1; i < n; i++){
    if (A[i] - A[i-1] > 1)
      return false;
  }
  return true;
}
    • 3

  2. 这是提出的解决方案：

    private static boolean check(int[] array, int k) {
    if (k == 0 && array.length > 0)
        return false;

    if (array[array.length - 1] != k || array[0] != 1)
        return false;

    for (int number = 1; number <= k; number++)
        if (Arrays.binarySearch(array, number) < 0)
            return false;

    return true;
}

    渐近复杂度O(n*log(n))肯定会更快

    更新

    适用的解决方案O(N)

    private static boolean check(int[] array, int k) {
    if (k == 0 && array.length > 0)
        return false;

    if (array[array.length - 1] != k || array[0] != 1)
        return false;

    int index = 0;
    int number = 1;
    while (number <= k) {
        while (index < array.length && array[index] == number)
            index++;

        if (array.length == index)
            return true;

        if (array[index] == number + 1)
            number++;
        else
            return false;

    }

    return true;
}
    • 2

  3. 编写一个 f-th，它将生成一个从 1 到 K（它是最大值）的数组。

    void count(int *array, int max)
{
    for (int i = 0; i < max; ++i)
    {
        array[i] = i+1;
    }
}

    ，然后在正文中，它将检查数组的第 i 个元素是否包含在给定数组 A. 中，如果它不包含至少一次 - 错误，如果一切正常 - 正确。

    • 1

  4. 实际上，您的问题是集合比较问题：

    public boolean function(int[] a, int k) {
    if (a.length < k) {
        return false;
    }
    Set<Integer> set = Arrays.stream(a).boxed().collect(Collectors.toSet());
    return set.size() == k && IntStream.range(1, k + 1).allMatch(set::contains);
}
    • 1

相关问题