java - 确定列表编号是否是连续的

Question

我在 Java 中工作。我有 5 个数字的无序列表，范围从 0 到 100，没有重复。我想检测其中 3 个数字是否是连续的，没有间隙。

例子：

[9,12,13,11,10] true
[17,1,2,3,5] true
[19,22,23,27,55] false

至于我尝试过的，还没有。如果我现在写它，我可能会采用最天真的方法对数字进行排序，然后反复检查序列是否存在。

Answer 1

int sequenceMin(int[] set) {
    int[] arr = Arrays.copy(set);
    Arrays.sort(arr);
    for (int i = 0; i < arr.length - 3 + 1; ++i) {
        if (arr[i] == arr[i + 2] - 2) {
            return arr[i];
        }
    }
    return -1;
}

这对数组进行排序并使用上面的 if 语句查找所需的序列，返回第一个值。

---

不排序：

（@Pace 提到了不排序的愿望。）有限的范围可以使用有效的“布尔数组”，BitSet。迭代nextSetBit很快。

    int[] arr = {9,12,13,11,10};
    BitSet numbers = new BitSet(101);
    for (int no : arr) {
        numbers.set(no);
    }
    int sequenceCount = 0;
    int last = -10;
    for (int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1)) {
        if (sequenceCount == 0 || i - last > 1) {
            sequenceCount = 1;
        } else {
            sequenceCount++;
            if (sequenceCount >= 3) {
                System.out.println("Sequence start: " + (last - 1));
                break;
            }
        }
        last = i;
    }
    System.out.println("Done");

Answer 2

非常幼稚（但更快）的算法：（你的数组是 input[]，假设它只包含你所说的 0-100 个数字）

int[] nums=new int[101];
for(i=0;i<N;i++) 
   {
   int a=input[i];
   nums[a]++;
   if (a>0) { nums[a-1]++; }
   if (a<100) { nums[a+1]++; }
   }

然后看是否有nums[]==3的元素。

使用一些 HashMap 而不是数组可能会更快（并消除 0-100 的限制）

---

编辑：唉，如果两个数字在初始序列中可能相等，这将不起作用

Answer 3

此代码似乎正在实现您的要求：

public class OrderdedList {
    public static void main(String[] args) {
        System.out.println(orderedWithNoGap(Arrays.asList(9, 12, 13, 11, 10))); // true
        System.out.println(orderedWithNoGap(Arrays.asList(17,1,2,3,5))); // true
        System.out.println(orderedWithNoGap(Arrays.asList(19,22,23,27,55))); // false
    }

    private static boolean orderedWithNoGap(List<Integer> list) {       
        Collections.sort(list);
        Integer prev = null;
        int seq = 0;
        for(Integer i : list) {
            if(prev != null && prev+1 == i)
                seq = seq == 0 ? 2 : seq+1;
            prev = i;
        }
        return seq >= 3;
    }

}

Answer 4

分配一个大小为 100 的数组：

private static final int MAX_VALUE = 100;

public boolean hasSequence(int [] values) {
  int [] bigArray = new int[MAX_VALUE];

  for(int i = 0; i < values.length; i++) {
    bigArray[values[i]] = 1;
  }

  for(int i = 0; i < values.length; i++) {
    index = values[i];
    if(index == 0 || index == MAX_VALUE-1) {
      continue;
    }
    if(bigArray[index-1] == 1 && bigArray[index+1] == 1) {
      return true;
    }
  }

  return false;
}

Answer 5

一般算法步骤。

Step 1. Sort the array.
Step 2. There are only 3 possible groups of 3 (next to each other) in an array of length five.
indexes 0,1,2 - 1,2,3 - 2,3,4.
Step 3. Check these 3 combinations to see if the next index is 1 more than the current index.

Answer 6

正如 OP 在评论中指出的那样，他想检查列表是否包含 3 个或更多序列号

public class WarRoom {

    static final int seqCount = 3;

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>((Arrays.asList(9, 11, 123, 511, 10)));
        for (int i : list) {
            if (seqNumbers(list, i, 0) >= seqCount) {
                System.out.println("Lucky Numbers : " + (i++) + "," + (i++) + "," + i);
            }
        }
    }

    public static int seqNumbers(List<Integer> list, int number, int count) {
        if (list.contains(number)) {
            return seqNumbers(list, number + 1, count + 1);
        }
        else {
            return count;
        }
    }
}

它不是最有效的解决方案之一，但我喜欢递归！

Answer 7

尚未对此进行测试，但对于较小的内存占用，您可以使用 BitSet

private static boolean consecutive(int[] input) {
    BitSet bitSet = new BitSet(100);
    for (int num : input) {
        bitSet.set(num);
    }

    bitSet.and(bitSet.get(1, bitSet.length())); // AND shift left by 1 bit
    bitSet.and(bitSet.get(1, bitSet.length())); // AND shift left by 1 bit

    return !bitSet.isEmpty();
}