Найти второе наименьшее значение вектора

Question

Я разработал процедуру, которая должна принять аргумент, вектор с числами в качестве записей, а затем вернуть самое низкое значение.

(define min-number 
    (lambda (vec) 
    (define looping 
     (lambda (i v-min) 
     (if (= i (vector-length vec)) 
      v-min 
      (looping (+ i 1) (min v-min (vector-ref vec i)))))) 
    (looping 1 (vector-ref vec 0)) 

    ) 
) 

Теперь я хочу построить процедуру, которая возвращает второе наименьшее значение вектора. Это то, что нужно сделать без преобразования вектора в список. Любые идеи о том, как я могу это сделать? Я не могу вытащить голову из «перечня». Моя голова говорит мне «использовать автомобиль», «использовать cdr» и т. Д., Который не работает в этом конкретном случае. Поэтому любые идеи были бы весьма признательны. Хмм, я думаю, что я все покрыл, если что-то неясно, дайте мне знать.

Спасибо :)

Answer 1

Если вы разрешили использовать встроенные функции, вот простой способ: найти минимальное значение, а затем искать следующее минимальное значение, которое является не что минимум. Это то, что я имею в виду:

(define min-number 
    (lambda (vec) 
    (let ((min-val (vector-argmin identity vec))) 
     (vector-argmin 
     (lambda (x) (if (equal? x min-val) +inf.0 x)) 
     vec)))) 

Например:

(min-number '#(5 4 1 2 3)) 
=> 2 

Answer 2

найти -ю наименьший элемент вектора хорошо решается с помощью алгоритма Быстрый выбор.

(define (quickselect A k) 
    (define pivot (list-ref A (random (length A)))) 
    (define A1 (filter (curry > pivot) A)) 
    (define A2 (filter (curry < pivot) A)) 
    (cond 
    [(<= k (length A1)) (quickselect A1 k)] 
    [(> k (- (length A) (length A2))) (quickselect A2 (- k (- (length A) (length A2))))] 
    [else pivot])) 

(quickselect '(9 8 7 6 5 0 1 2 3 4) 2) ; => 1 

код из http://rosettacode.org/wiki/Quickselect_algorithm#Racket

Answer 3

Другой подход, аналогичный ответ OSCAR в том, что оба O (N). Это работает для любых последовательностей, включая списки и векторы!

(define (second-lowest seq) 
    (define-values (_ x) 
    (for/fold ((a #f) (b #f)) 
       ((x seq)) 
     (cond ((< x (or a (add1 x))) (values x a)) 
      ((< x (or b (add1 x))) (values a x)) 
      (else (values a b))))) 
    x) 

Answer 4

Вот две версии vector-select которая находит -го наименьшего элемента в векторе v. Это означает, что (vector-select v 1) находит второй наименьший элемент в векторе. Разница между vector-select и vector-select! заключается в том, что последний может изменить порядок элементов в векторе. Обе процедуры имеют ожидаемое время O(n), где n - длина вектора.

#lang racket 
; vector-ref and vector-set! is used so often, so introduce shorter notation 
(define-syntax-rule (vref v i) (vector-ref v i)) 
(define-syntax-rule (vset! v i e) (vector-set! v i e)) 

; vector-select : vector index -> number 
; find the kth largest element of v 
; (where 0 <= k < n) 
(define (vector-select v k) 
    (define n (vector-length v)) 
    (unless (<= 0 k (- n 1)) 
    (error 'vector-select "expected a number between 0 and the length of the vector")) 
    (subvector-select! (vector-copy v) k 0 n)) 

; vector-select! : vector index -> number 
; find the kth largest element of v 
; (where 0 <= k < n) 
; side effect: the order of the elements may change 
(define (vector-select! v k) 
    (define n (vector-length v)) 
    (unless (<= 0 k (- n 1)) 
    (error 'vector-select! "expected a number between 0 and the length of the vector")) 
    (subvector-select! v k 0 n)) 

; subvector-select : vector index index index -> number 
; find the kth largest element of the elements v[s],v[s+1],...,v[t-1]. 
; assumption: s<t (i.e. the subvector is non-empty) 
(define (subvector-select! v k s t) 
    (define n (- t s)) ; length of subvector 
    (cond 
    [(= n 1) (unless (= k 0) (error "Error 1")) 
      (vref v s)] 
    [else (define r (randomized-partion! v s t)) ; v[r] is a pivot 
      (define l (- r s))      ; number of elements left of pivot (in subvector) 
      (cond 
       [(= k l) (vref v r)]        ; found it! 
       [(< k l) (subvector-select! v k  s r)]  ; the element is left of the pivot 
       [else (subvector-select! v (- k l) r t)])])) ; the element is right of the pivot 

; randomized-partion! : vector index index -> index 
; Pick a random index between s and t, then partion the elements 
; in the subvector v[s],v[s+1],...,v[t-1] using v[r] as pivot. 
; I.e. move elements smaller than the pivot to appear before the pivot 
; and move elements larger than the pivot to appear after the pivot. 
; Finally return the index of the pivot. 
(define (randomized-partion! v s t) 
    ;; Helper 
    ; swap! : index index -> void 
    ; swap elements with index i and j 
    (define (swap! i j) 
    (define vi (vref v i))   
    (vset! v i (vref v j))   
    (vset! v j vi)) 
    ;; Main 
    (define r (+ s (random (- t s)))) ; pick random pivot index in subvector 
    (define p (vref v r))    ; the pivot value 
    (swap! (- t 1) r)     ; place the pivot as the last value in the subvector 
    (define i s)      ; invariant: all elements before v[i] are <= pivot 
    (for ([j (in-range s (- t 1))]) ; loop through all elements (except the pivot) 
    (when (<= (vref v j) p)   ;  if the element is non-greater than the pivot 
     (swap! i j)     ;  move it to the front of the subvector 
     (set! i (+ i 1))))   ;  and update i to the next available slot 
    (swap! i (- t 1)) 
    i)        ; finally put the pivot in place