Common Lisp에서 가장 작은 숫자와 두 번째 작은 숫자 사이의 범위는 어떻게 얻을 수 있습니까?

Question

커먼 리스프에서 가장 작은 수와 두 번째로 작은 수 사이의 범위를 나타내는 함수를 만들고 있습니다.

이 함수는 가장 작은 숫자와 가장 큰 숫자를 만들 수 있습니다. (나는 그것을 검사했다). 그러나이 기능은 목록에서 '두 번째로 작은 숫자'를 만들 수 없습니다 ...

이 문제를 해결하기 위해 고려해야 할 사항은 무엇입니까? 이 기능을 수행하는 데 필요한 충분한 조건을 충족 시켰다고 생각합니다.

큰 도움이 필요합니다. 이 결과는 다음과 같아야

는

(내 범위는 '2 3 1 (0-7 10)) => (-1 10)

이 I 지은 내 코드 .

(defun my-range (list-of-numbers) 
    (let ((largest (first list-of-numbers))     
      (smallest (first list-of-numbers))     
      (secsmallest (first list-of-numbers)))    
     (dolist (element1 (rest list-of-numbers) largest)  
     (when (> element1 largest) 
      (setf largest element1))) 
     (dolist (element2 (rest list-of-numbers) smallest) 
     (when (< element2 smallest) 
      (setf smallest element2))) 
     (dolist (element3 (remove smallest list-of-numbers) secsmallest) 
     (when (< element3 secsmallest) 
      (setf secsmallest element3)) 
     (return (list (- smallest secsmallest) largest))))) 

Answer 1

목록에서 두 개의 가장 작은 요소를 가져 오려면 한 번에 작업 할 수 있습니다. 우리는 지금까지 본 두 가지 가장 작은 값의 목록을 유지합니다. 우리가 항목을 스캔 할 때, 우리는 순서대로이 목록에 삽입합니다. 항상 세 번째로 작은 값을 버립니다. 우리가 끝나면 두 개의 가장 작은 값의 목록이 있습니다. (또는 0 값들의 목록 또는 하나 개의 값의리스트가있는 경우에만 많은.)

가 N의 uordered리스트 밖으로 K 작은 값을 선택하기위한 효율적인 알고리즘이있다 : quickselect .

o (n log n) 성능에 신경 쓰지 않는다면 전체 목록을 정렬하고 결과에서 처음 두 값을 선택할 수 있습니다.

우리가 정확히 두 개의 항목이 라인을 따라 하드 코딩 할 수 있습니다 원하는 상황 :

이

(defun least-two (list) 
    (cond 
    ((null list) nil) 
    ((null (cdr list)) (car list)) 
    (t (let ((a (car list)) 
      (b (cadr list))) 
     (unless (< a b) 
     (rotatef a b)) 
     (dolist (el (cddr list) (values a b)) 
     (cond 
      ((< el a) (shiftf b a el)) 
      ((< el b) (setf b el)))))))) 

아주 쉽게 : 나는 SE 브라우저 편집기에서 개 입력 당신이 그것을 볼 정확하게,이 닫혀 저장 괄호와 잘 작동하는 것 같습니다. :)

values을 사용하여 목록 대신 여러 값을 반환했습니다. 목록을 원하면 (list a b)으로 변경하고 주의 두 번째 사례는 (car list) 대신 list을 반환해야합니다. 하나의 dolist와

Answer 2

나이브 구현 :

(defun my-range (list-of-numbers) 
    ;; I don't know what should be returned if NIL is given 
    (check-type list-of-numbers cons) 
    (let* ((min (first list-of-numbers)) 
     (min2 nil) 
     (max min)) 
    (dolist (num (rest list-of-numbers) (list (- min (or min2 max)) max)) 
     (if (<= num min) 
      (setf min2 min 
       min num) 
      (if (<= max num) 
       (setf max num) 
       (setf min2 num)))))) 

(my-range '(0 7 8 2 3 -1)) 
;=> (-1 8) 
(my-range '(-1 0 0 0 0)) 
;=> (-1 0) 
(my-range '(-1 0 0 0 -1)) 
;=> (0 0) 
(my-range '(0)) 
;=> (0 0) 

Answer 3

난 그냥 이외의 효율성을 떠나 먼저 작업 솔루션을 작성합니다

정렬 목록의 사본은 앞의 작은 요소가 다음에 처음 두 숫자를 선택하십시오.

(defun two-smallest-numbers (input-list) 
    (subseq (sort (copy-list input-list) #'<) 0 2)) 

CL-USER 20 > (two-smallest-numbers '(83 3735 44562 483 83 2223 42232 3322)) 
(83 83) 

또는 가장 작은 다른 번호를 반환합니다. 가장 작은 숫자를 찾아서 목록에서 제거하고 가장 작은 숫자를 다시 찾습니다. 두 숫자를 모두 반환하십시오.

CL-USER 22 > (defun two-smallest-different-numbers (input-list) 
       (flet ((smallest-number (list) 
         (reduce #'min list))) 
       (let ((s0 (smallest-number input-list))) 
        (list s0 (smallest-number (remove s0 input-list)))))) 
TWO-SMALLEST-NUMBERS 

CL-USER 23 > (two-smallest-different-numbers '(83 3735 44562 483 83 2223 42232 3322)) 
(83 483)