如何检查列表中的所有数字是否稳步增加？

Question

我有几个包含简单,正整数的长度不同的列表,(2 4 1 3)我希望在列表排序后检查所有数字是否相互跟随.这意味着订单本身无关紧要,但不允许存在间隙.

(2 4 1 3) 是正确的

(2 4 1 5) 不正确

在我开始重新发明轮子之前,我想知道是否有替代方法对列表进行排序,然后检查第一个和第二个(等等......)元素的差异是否为1.

编辑

我的例子没有显示完整的任务.该列表不必1每次都开始,即(6 8 7 9)也可以是有效输入.

Answer 1

最优解

您需要检查列表定义的集合是否相同[a:b].这可以通过创建适当长度的位向量来轻松完成.这是线性(O(n)在列表长度)(需要一次用于扫描它length和min,一旦用于填充位向量),并且需要用于矢量一些额外的临时存储器:

(defun range-p (list)
  "Check that the list is identical to a..b as a set."
  (multiple-value-bind (min len)
      (loop for obj in list for len upfrom 0
        unless (integerp obj) do (return-from range-p nil)
        minimize obj into min
        finally (return (values min len)))
    (loop
      ;; 0: not seen this index in list yet
      ;; 1: already seen this index in list
      with indicator = (make-array len :element-type 'bit :initial-element 0)
      for obj in list for pos = (- obj min) do
        (unless (< pos len)
          ;; obj out of range
          (return-from range-p nil))
        (if (zerop (aref indicator pos))
            ;; obj is being seen for the 1st time; record that
            (setf (aref indicator pos) 1)
            ;; duplicate obj
            (return-from range-p nil)))
    ;; all list elements are unique and in the right range;
    ;; injectivity + same cardinality for finite sets => surjectivity
    t))

测试:

(range-p '(2 4 1 3))
==> T
(range-p '(2 4 1 5))
==> NIL
(range-p '(-1 5 3 4 2 1 0))
==> T
(range-p '(-1 5 3 4 3 1 0))
==> NIL
(range-p '(2 4 1 a 5))
==> NIL

排序

排序是线性的(O(n*log(n))),因此显然不是最理想的.

PS

这可能与使用Lisp递归检查连续数字有关.