पायथन में किसी भी संख्या और उसकी अगली छोटी संख्या का अधिकतम अंतर खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, हमें किसी भी संख्या और अगली छोटी संख्या के बीच मौजूद अधिकतम अंतर को खोजना होगा। हमारा लक्ष्य इसे रैखिक समय में हल करना है।

इसलिए, यदि इनपुट संख्या =[14, 2, 6, 35, 12] की तरह है, तो आउटपुट 21 होगा, क्योंकि 35 और 14 में 21 का सबसे बड़ा अंतर है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• max_val :=अधिकतम अंक, min_val :=न्यूनतम अंक

• अगर max_val min_val के समान है, तो

  • वापसी 0

• डेल्टा:=(max_val - min_val) / (अंकों का आकार -1)

• min_map :=एक खाली नक्शा (यदि कुछ मान इंफ के रूप में वापसी मूल्य नहीं हैं)

• max_map :=एक खाली नक्शा (यदि कुछ मान −inf के रूप में वापसी मूल्य नहीं हैं)

• रेस:=0, आईडीएक्स:=0

• अंकों में प्रत्येक अंक के लिए, करें

  • idx :=((संख्या - min_val) / डेल्टा) का तल

  • max_map[idx] :=max_map[idx] और num का अधिकतम

  • min_map[idx] :=न्यूनतम min_map[idx] और num

• पिछला :=min_val

• मैं के लिए 0 से लेकर अंकों के आकार -1 तक के लिए, करें

  • अगर min_map[i] inf जैसा नहीं है, तो

    • रेस :=अधिकतम रेस और (min_map[i] - पिछला)

    • पिछला :=max_map[i]

• रिटर्न रेस

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

from collections import defaultdict
import math
class Solution:
   def solve(self, nums):
      max_val = max(nums)
      min_val = min(nums)
      if max_val == min_val:
         return 0
      delta = (max_val − min_val) / (len(nums) − 1)
      min_map = defaultdict(lambda: float("inf"))
      max_map = defaultdict(lambda: float("−inf"))
      res = 0
      idx = 0
      for num in nums:
         idx = math.floor((num − min_val) / delta)
         max_map[idx] = max(max_map[idx], num)
         min_map[idx] = min(min_map[idx], num)
      prev = min_val
      for i in range(len(nums)):
         if min_map[i] != float("inf"):
            res = max(res, min_map[i] − prev)
            prev = max_map[i]
      return res
ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))

इनपुट

[14, 2, 6, 35, 12]

आउटपुट

21