代码之家 › 专栏 › 技术社区 › Martin Buchmann

如何检查列表中的所有数字是否都在稳步增长?

common-lisp numbers list

Martin Buchmann · 技术社区 · 7 年前

我有几个不同长度的列表,包含简单的正整数,比如 (2 4 1 3) 在列表排序之后,我想检查所有的数字是否都跟随在一起。这意味着顺序本身并不重要,但不允许有间隙。

(2 4 4 1) 是正确的

(2 4 1 5) 不正确

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

编辑

我的示例没有显示完整的任务。列表不必以开头 一 每次,即, (6 8 7 9) 也可以是有效的输入。

3 回复 | 直到 7 年前

sds Niraj Rajbhandari 7 年前

最优解

您需要检查列表定义的集合是否与 [a:b] . 这很容易通过创建 bit vector 长度合适。这是 线性的 ( 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)) )因此明显是次优的。

聚苯乙烯

这可能与 Check consecutive numbers recursively using Lisp .

Martin Buchmann 7 年前

把SDS的回答和Renzo的评论结合起来,我最终得出了对我有用的结论:

(defun min-obj (list)
   (loop with min = most-positive-fixnum ; sufficient in my case
         for obj in list
         when (< obj min)
           do (setf min obj)
         finally (return min))) 

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

谢谢!

DHARMENDRA SINGH 7 年前

您可以使用一些自然数(如中的扫描列表)来数学地解决这个问题。 o(n) 求最小、最大、长度和总和,然后用这个公式计算自然数和

 actualMax = min+(length(list)-1)
    nSum = ((actualMax -min+1)/2)*(actualMax +min)
    nSum-total==0?"yes":"no"

让我们考虑一下

Ex -1 (6,8,7,9) min = 6 actual max = 6+(4-1) = 9,max=9, total = 30 naturalSum = 30 it is true
Ex-2 (6,8,7,10) min = 6 actual max = 6+(4-1) = 9,max=10, total = 31 naturalSum = 30 it is false