java - 测试长度为 n 的未排序整数列表是否表示集合 {1,...,n}

Question

现在我有以下解决方案，我认为这是相当清楚的。

import java.util.Arrays;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

public class ConsecutiveNumbers {
  public static void main(String[] args) {
    List<Integer> good = Arrays.asList(2, 1);
    System.out.println(is1ToN(good)); // true

    List<Integer> bad1 = Arrays.asList(3, 1);
    System.out.println(is1ToN(bad1)); // false

    List<Integer> bad2 = Arrays.asList(1, 1, 2);
    System.out.println(is1ToN(bad2)); // false
  }

  public static boolean is1ToN(List<Integer> numbers) {
    SortedSet<Integer> set = new TreeSet<>(numbers);
    return set.isEmpty() || (set.size() == numbers.size() && set.first() == 1
        && set.last() == set.size());
  }
}

有没有更好(更有效或更清晰)的解决方案？

Answer 1

创建一个大小为 N 的 boolean 数组 p。遍历列表，依次考虑列表中每个元素的值 v。如果 v 超出范围 1...n，则返回 false。如果 p[v-1] 为真，则您有一个重复值，因此答案为假。否则，将 p[v-1] 设置为真。如果到达列表末尾，则返回 true。

使用 BitSet 代替数组可能值得也可能不值得。这将节省一些内存，尽管所需的额外内存仍然是 O(N)。但是会增加CPU的工作量。这笔交易是否值得取决于用例。