如何检查列表中的所有数字是否都在稳定增加? [英] How to check if all numbers in a list are steadily increasing?

问题描述

我有几个长度不等的列表，其中包含简单的正整数，例如(2 4 1 3)，我想检查列表排序后是否所有数字都紧跟在后.这意味着顺序本身并不重要，但不允许有任何差距.

I have several lists of varying length containing simple, positive integers, like (2 4 1 3) and I want to check whether or not all numbers are following each other after the list is sorted. This means the order itself doesn't matter but there are no gaps allowed.

(2 4 1 3)是正确的

(2 4 1 5)不正确

在我重新发明轮子之前，我想知道是否有一种方法可以对列表进行排序，然后检查第一个元素与第二个元素的区别(依此类推...)是1.

Before I start to re-invent the wheel, I would like to know if there is an alternative to sorting the list and then checking whether or not the difference of the first and the second (and so on...) element is 1.

编辑

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

My example was not showing the complete task. The list does not have to start with 1 each time, i.e., (6 8 7 9) could also be a valid input.

推荐答案

最佳解决方案

您需要检查列表定义的集合是否与[a:b]相同. 通过创建适当长度的位向量即可轻松完成此操作. 列表长度为线性(O(n))(需要对其进行一次扫描，以扫描

Optimal Solution

You need to check whether the set defined by the list is identical to [a:b]. This is easily done by creating a bit vector of the appropriate length. This is linear (O(n)) in list length (requires scanning it once for length and min, and once for filling the bit vector), and requires some extra temporary memory for the vector:

(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)))，因此显然次优.

Sorting

Sorting is linearithmic (O(n*log(n))) and thus clearly suboptimal.

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

这篇关于如何检查列表中的所有数字是否都在稳定增加?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！