Làm cách nào tôi có được khoảng cách tối thiểu giữa các yếu tố Danh sách?

Question

Ví dụ giả sử tôi có một danh sách được sắp xếp

val sắp xếp = Danh sách (1, 5, 15, 37, 39, 42, 50)

Khoảng cách nhỏ nhất là (39-37) = 2. Làm thế nào tôi có được kết quả này? Tôi đã được nhìn foldLeft tôi nhận được những cảm giác nó cũng tương tự như những gì tôi cần, nhưng không hoàn toàn đúng đắn

Answer 1

val sorted = List(1, 5, 15, 37, 39, 42, 50) 
(sorted.tail,sorted).zipped.map(_-_).min 
//res2: Int = 2 

[Chỉnh sửa]

Bạn có thể sử dụng một lần cũng như:

sorted.tail.foldLeft((sorted.head,Int.MaxValue))((x,y) => (y, math.min(y-x._1,x._2)))._2 

Answer 2

Dưới đây là những gì tôi sẽ làm gì:

1. viết một chức năng cho phép bạn biến một danh sách các số n vào một danh sách các (n - 1) khoảng trống

2. ghi/sử dụng một chức năng chọn số nhỏ nhất từ ​​một danh sách

Đừng quên để xử lý các trường hợp danh sách trống f hoặc phần 1! (Ngẫu nhiên, Phần 2 có thể được viết thành một nếp gấp).

Answer 3

val sorted = List(1, 5, 15, 37, 39, 42, 50) 

sorted match { 
    case Nil => None 
    case List(a) => None 
    case l => Some(l.sliding(2).map{case Seq(a, b) => math.abs(a - b)}.min) 
} 
// res1: Option[Int] = Some(2) 

sliding trả về trình lặp, do đó chỉ nên duyệt qua danh sách một lần.

Nếu bạn muốn tìm hai yếu tố nào có khoảng cách nhỏ nhất, bạn cũng có thể sử dụng minBy. Vì vậy, đây là một biến thể khác, chỉ để cho vui.

sorted.view.zip(sorted.tail).minBy(t => math.abs(t._1 - t._2)) 
// res4: (Int, Int) = (37,39) 

Answer 4

Imperative (và có thể nhanh hơn) phiên bản:

if (sorted.isEmpty) { 
    None 
    } else { 
    var sortedTail = sorted.tail 
    if (sortedTail.isEmpty) { 
     None 
    } else { 
     var minDiff = Int.MaxValue 
     var prev = sorted.head 
     do { 
     val curr = sortedTail.head 
     minDiff = minDiff min math.abs(curr - prev) 
     sortedTail = sortedTail.tail 
     prev = curr 
     } while (!sortedTail.isEmpty) 
     Some(minDiff) 
    } 
    } 

Answer 5

Sử dụng gập lại Trái:

sorted match {  
     case Nil | List(_) => None 
     case x :: xs => Some(
     (xs.foldLeft((Integer.MAX_VALUE, x)) { 
      case ((min, prev), next) => (math.min(min, next - prev), next) 
     })._1 
    ) 
    }