2011-11-11 12 views
6

उदाहरण के लिए मान लीजिए कि मैंमैं सूची तत्वों के बीच न्यूनतम अंतर कैसे प्राप्त करूं?

एक क्रमबद्ध सूची है वैल अनुसार क्रमबद्ध = सूची (1, 5, 15, 37, 39, 42, 50)

छोटी से छोटी खाई है (39-37) = 2। मैं इस परिणाम को कैसे प्राप्त करूं? मैं foldLeft को देखकर किया गया है मैं महसूस कर रही हो यह मैं क्या जरूरत के समान है लेकिन नहीं बहुत सही बात

+1

यदि यह एक क्रमबद्ध सूची है जो मैट फेनविक ने एक पुनरावृत्ति में सुझाव दिया है। यह ओ (एन) समय खर्च होगा। minGap = minGap Gleeb

उत्तर

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

[संपादित करें]

साथ ही आप एक गुना का उपयोग कर सकते हैं:

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

यहाँ मैं क्या कर सकता:

  1. एक समारोह है कि n नंबरों की सूची बदल देती बारे में (n - 1) की एक सूची में अंतराल

  2. लिखने/एक समारोह है कि एक सूची से सबसे छोटी संख्या का चयन करता है का उपयोग

खाली सूची मामले च को संभालने के लिए मत भूलना या भाग 1! (संयोग से, भाग 2 को एक गुना के रूप में लिखा जा सकता है)।

+0

सीमा से बाहर नहीं जा सकें (1) लूप के बिना किया जा सकता है? मैं एक कार्यात्मक समाधान – deltanovember

+0

@deltanovember का उपयोग करने की कोशिश कर रहा था - बेशक! ऐसा करने के लिए बहुत सारे कार्यात्मक तरीके हैं 1. एक तरीका रिकर्सन का उपयोग करेगा! –

12
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 पुनरावर्तक देता है, ताकि केवल सूची एक बार पार करना चाहिए।

आप जो दो तत्वों छोटी से छोटी खाई है खोजने के लिए रुचि रखते हैं, आप भी minBy उपयोग कर सकते हैं। तो बस मस्ती के लिए, एक और भिन्नता है।

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

पहल (और संभव तेज) संस्करण:

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) 
    } 
    } 
1

का उपयोग करना तह बाएं:

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 
    ) 
    } 
संबंधित मुद्दे