min2 :: Ord a => [a] -> a
min2 x =  if g  == minimum x then minimum x else g
  where
    g = minimum(filter (> minimum x) x)

यह केवल उस सूची के लिए काम करता है जहां केवल एक न्यूनतम मान होता है; तो min2 [2110, 4820, 2110, 4120] != 2110, यह 2110 को एक तत्व के रूप में गिना जाता है 2 नहीं

कोड मेरे पास अभी है, मैं दोहराए गए तत्व के लिए कैसे खाता कर सकता हूं

0
Shifter 17 अप्रैल 2020, 09:03
6
क्यों न सिर्फ दूसरे तत्व को छाँटें और लें? BTW, if g == minimum x then minimum x else g तार्किक रूप से केवल g के समान है, कोई फर्क नहीं पड़ता कि g क्या है, और यह इस तथ्य से जुड़ा नहीं है कि आप न्यूनतम ले रहे हैं।
 – 
Robin Zigmond
17 अप्रैल 2020, 09:12
अधिमानतः मैं फ़िल्टर या फ़िल्टर का उपयोग करता हूं, और मैं उम्मीद कर रहा था कि न्यूनतम तत्व को एक के रूप में नहीं गिना जाएगा
 – 
Shifter
17 अप्रैल 2020, 09:18
2
"क्यों न केवल क्रमबद्ध करें" - ठीक है, O (n · log n) एक उचित कारण होगा कि क्यों नहीं। तो, इस टिप्पणी में यह जोड़ना महत्वपूर्ण है कि हास्केल आलस्य से बचने में सक्षम है।
 – 
leftaroundabout
17 अप्रैल 2020, 10:03
4
यदि sort को मर्ज सॉर्ट के रूप में कार्यान्वित किया जाता है, तो आलस्य के लिए धन्यवाद यह वास्तव में एक प्रकार के ढेर प्रकार के रूप में चलाया जाता है (मुझे याद है कि इस पर बहुत समय पहले चर्चा की जा रही थी)। ऐसे मामले में, इसकी अच्छी संपत्ति होगी कि पहले के तत्वों की मांग करने पर केवल ओ (एन · लॉग के), आईआईआरसी खर्च होता है। जब k=2, वह O(n) है जो इष्टतम है। हालांकि, यह तथ्य बिल्कुल स्पष्ट नहीं है, और इस बारे में एक अच्छा उदाहरण है कि जटिलता के बारे में सटीक तरीके से तर्क क्यों हास्केल में कठिन हो सकता है।
 – 
chi
17 अप्रैल 2020, 10:34

2 जवाब

पहले सूची को क्रमबद्ध करें और फिर परिणामी मध्यवर्ती सूची (यदि कोई हो) के दूसरे तत्व का चयन करें:

import Data.List (sort)

min2 :: Ord a => [a] -> a
min2 xs = case sort xs of
  []           -> error "min2: empty list"
  [x]          -> error "min2: singleton list"
  (x : y : xs) -> y
> min2 [2110, 4820, 2110, 4120]
2110

या, यदि आप अधिक स्पष्ट रैखिक-समय समाधान चाहते हैं, तो आप बस इनपुट सूची को पार कर सकते हैं और एक संचित पैरामीटर बनाए रख सकते हैं जो अब तक सामने आए दो सबसे छोटे मानों को संग्रहीत करता है:

data Acc a = Empty | Singleton a | Min2 a a

min2' :: Ord a => [a] -> a
min2' = fromAcc . foldl go Empty
  where
    go Empty x         = Singleton x
    go (Singleton y) x
      | x < y          = Min2 x y
      | otherwise      = Min2 y x
    go (Min2 y z) x
      | x < y          = Min2 x y
      | x < z          = Min2 y x
      | otherwise      = Min2 y z

    fromAcc Empty         = error "min2': empty list"
    fromAcc (Singleton x) = error "min2': singleton list"
    fromAcc (Min2 x y)    = y
> min2' [2110, 4820, 2110, 4120]
2110
1
Stefan Holdermans 21 अप्रैल 2020, 13:39
आपका पहला फ़ंक्शन, min2, भी रैखिक है, क्योंकि sort को मर्जसॉर्ट के रूप में लागू किया गया है। तुलना के निहित पेड़ में O(n) नोड्स होते हैं, जो O(n) समय में बॉटम-अप तरीके से बनाया जाता है, और सॉर्ट किए गए परिणाम का प्रत्येक तत्व उत्पन्न होता है O(log n) समय में।
 – 
Will Ness
21 अप्रैल 2020, 09:44
धन्यवाद, @WillNess, आप बिल्कुल सही कह रहे हैं। यह सिर्फ इतना है कि sort के माध्यम से रैखिकता कम स्पष्ट है; मैं तदनुसार जवाब अपडेट कर दूंगा। (इसके अलावा, कोई इसे sort का एक कार्यान्वयन विवरण मान सकता है क्योंकि Data.List.sort के लिए प्रलेखन छँटाई विधि को अनिर्दिष्ट छोड़ देता है।)
 – 
Stefan Holdermans
21 अप्रैल 2020, 13:38

आप आइटम्स की सूची को सॉर्ट कर सकते हैं, और फिर दूसरा आइटम चुन सकते हैं। उदाहरण के लिए:

import Data.List(sort)

min2 :: Ord a => [a] -> Maybe a
min2 xs
    | (_:x:_) <- sort xs = Just x
    | otherwise = Nothing

sort फ़ंक्शन को आलसी विलय जहां यह पहले [src] कुछ अतिरिक्त अनुकूलन के साथ होता है। इसका मतलब है कि यदि आप उदाहरण के लिए k-th तत्व प्राप्त करते हैं, तो यह *O(*k×log n+n) समय में चलेगा, इसलिए दूसरे आइटम के लिए, यह O(n) में चलेगा।

0
Willem Van Onsem 19 अप्रैल 2020, 00:20