algorithm - सरणी और चाबी को देखते हुए, उसके बाएं और दाएं उप सरणी में छोटे या उसके बराबर तत्वों की संख्या पाएं?




language-agnostic (3)

मुझे बाएं और दाएं उपस्करों में सरणी के i -th तत्व से छोटा या उसके बराबर तत्वों की संख्या मिलनी होगी i

उदाहरण के लिए यदि मेरी सरणी है

A[]=4 3 5 2 2 5

मेरे 2 एरेज़ होंगे

0 0 2 0 0 5

तथा

3 2 3 1 1 0

प्रथम सरणी के I- तत्व तत्व i -th तत्व के बाईं ओर से i -th तत्व से छोटा या उसके बराबर तत्वों की संख्या को दर्शाता है।

द्वितीय सरणी का I- अंग तत्व i -th तत्व के दाईं ओर से i -th तत्व से छोटा या उसके बराबर तत्वों की संख्या को दर्शाता है।

मैं इन सरणियों को ( एन 2 ) में दो छोरों का उपयोग कर पा सकता हूं I

क्या यह ( एन ) में किया जा सकता है?


नहीं, यह O(n) समय में ऐसा करना संभव नहीं है। सबसे अच्छा आप कर सकते हैं O(n log n)

यहाँ सबूत है मान लीजिए मूल सरणी में विशिष्ट तत्व हैं। आइए हम पहले सरणी के लिए कितने संभावनाएं हैं, जो आप चाहते थे (दूसरे के लिए एक प्रमाण समान है)। पहली संख्या ( 0 ) के लिए 1 संभावना है 2 नंबर ( 0 या 1 ) के लिए 2 संभावनाएं हैं तीसरी संख्या ( 0 , 1 या 2 ) के लिए 3 संभावनाएं हैं, और इसी तरह। यह निम्नानुसार है कि अधिक से अधिक 1 * 2 * 3 * ... * n = n! संभावित उत्तर। वास्तव में यह देखना आसान है कि इनमें से प्रत्येक संभावित उत्तर के लिए कम से कम एक अलग सरणी की संख्या है जो इसे पैदा करती है (बाएं से दाएं कार्य करें। यदि answer[i] 0 होना है, तो original[i] निर्धारित करें पहले से चुने गए सभी नंबरों की तुलना में छोटा है। यदि answer[i] है, तो original[i] को सभी पहले से चुने गए नंबरों से अधिक होना चाहिए। अन्यथा, original[i] को i छोटा होना चाहिए और (i+1) - सबसे छोटी संख्या पहले से ही चुना गया है)। किसी भी एल्गोरिथ्म को n! की पहचान करना चाहिए n! संभव उत्तर सही है यदि हम हमेशा f(n) तुलना के साथ एल्गोरिथ्म को समाप्त कर सकते हैं तो यह 2^f(n) >= n! (प्रत्येक तुलना में केवल 2 संभव परिणाम होते हैं क्योंकि मूल संख्या सभी अलग थीं)। दोनों पक्षों के लॉग (आधार 2) लेते हुए हमें f(n) >= log(n!)log(n!) लिए स्टर्लिंग के सन्निकटन का उपयोग करते हुए हम देखते हैं कि हम O(n log n) तुलना से बेहतर नहीं कर सकते।

O(n log n) समय में करना संभव है। निम्नलिखित जावा विधि (जो O(n log n) समय में नहीं चलती है O(n log n) आपको आवश्यक पहली एरे देता है (दूसरा एक ही किया जा सकता है)। Arrays.sort() TimSort का उपयोग करता है जो O(n log n) । हालांकि, O(n log n) समय में पूरी पद्धति को चलाने के लिए, आपको List क्रियान्वयन के साथ ArrayList को प्रतिस्थापित करना होगा, जहां विधियां add(Object object) remove(int index) , remove(int index) और अंतिम remove(int index) add(Object object) को remove(int index) O(log n) समय में चलाना Http://www.nayuki.io/page/avl-tree-list के अनुसार, AvlTreeList O(log n) समय में add() और add() को remove() , और एक " AvlTreeList " बढ़ाने के लिए संभव है ताकि खोजों O(log n) भी हैं यह साबित करता है कि आपके एरे O(n log n) समय में पाये जा सकते हैं

public static int[] firstArray(int[] arr) {
    int[] copy = arr.clone();
    Arrays.sort(copy);
    List<Integer> list = new ArrayList<>();
    for (int a : copy)
        list.add(a);
    int length = arr.length;        
    int[] temp = new int[length];
    for (int i = length - 1; i >= 0; i--) {
        int j = list.lastIndexOf(arr[i]);
        temp[i] = j;
        list.remove(j);
    }
    return temp;
}

मैं रैंक फ़ील्ड के साथ एक संतुलित द्विआधारी पेड़ को बुलाए गए कुछ चीज़ों के जरिए @ pbabcdefp के उत्तर को आसान बना देता हूं (देखें Knuth 6.2.3, रैखिक सूची प्रतिनिधित्व)। एक संतुलित वृक्ष पर विचार करें (कार्यान्वयन कोई फर्क नहीं पड़ता, इसलिए लाल-काला या एवीएल ठीक हो जाएगा) फिर भी हमारे पास एक अतिरिक्त क्षेत्र है जिसे rank कहा जाता है जो बायां उप-प्रक्षेपण के आकार को संग्रहीत करेगा, संख्या हमारे पेड़ में डाली जाएगी सबसे बड़ा आदेश से सबसे छोटा, प्रत्येक प्रभावित नोड के लिए रैंक फ़ील्ड को प्रत्येक प्रविष्टि / रोटेशन के बाद अपडेट किया जाता है। हम अपने संतुलित पेड़ में डुप्लिकेट तत्वों की अनुमति देंगे।

एल्गोरिदम ए:
  1. रूट नोड के लिए head सेट करें हमारे द्वारा खोज रहे मूल्य के लिए v सेट करें i v लिए सूची में सूचकांक v , यह हमारा रिटर्न वैल्यू होगा।
  2. अगर head रिक्त / रिक्त है, सूचकांक के साथ सफलतापूर्वक वापस लौटें i
  3. अगर v < head.value , तब head <- head.left , अन्यथा i <- i + head.rank + 1 और head <- head.right
  4. 2 पर वापस जाएं
मूल एल्गोरिदम :

सरणी में प्रत्येक तत्व के लिए: एल्गोरिथ्म का उपयोग करें ऊपर वर्णित तत्वों की संख्या (जो कि वृक्ष में है और इस प्रकार वर्तमान तत्व से पहले आया है) को खोजने के लिए, इसके बाद के संस्करण या उसके बराबर है, फिर संशोधित प्रविष्टि का उपयोग करके इसे हमारे पेड़ में जोड़ें। यह पहले सरणी देता है एक बार दोबारा दोहराएं, इस बार अग्रेषित करने के बजाय पीछे की ओर सरणी पर चलने के लिए, दूसरी सरणी प्राप्त करें।


ऐसा लगता है कि आप निद्रा पर कूद नहीं सकते हैं तो बुनियादी संस्करण बस होगा:

def naive(arr)
  res = Array.new(arr.size,0)
  for i in 0..arr.length-1
    for j in i+1..arr.length-1
      res[i] += 1 if arr[i] >= arr[j]
    end
  end
  res
end

हालांकि आपके डेटा सेट के आधार पर आप कुछ अनुकूलन कर सकते हैं आपके उदाहरण में उदाहरण के लिए पुनरावृत्तिएं हैं - हम उसी तथ्य का उपयोग कर सकते हैं ताकि समान नंबर के लिए सरंक्षण सरणी से दो बार न हो सके। ऐसे मामलों में वर्तमान की तुलना में कम संख्या की खोज करने के बजाय - आप वर्तमान (दाएं से बाएं) की तुलना में प्रत्येक संख्या के अतिरिक्त जोड़ सकते हैं और उन संख्याओं को अनदेखा कर सकते हैं जो पहले से उपयोग किए गए हैं:

def rightleft(arr)
  ignore = {}
  res = Array.new(arr.size,0)
  (arr.size-1).downto(0) do |i|
    current = arr[i]
    next if ignore[current]
    additor = 1
    (i-1).downto(0) do |j|
      if arr[i] <= arr[j]
        res[j] += additor
          if arr[i] == arr[j]
          additor += 1
          ignore[current] = true
        end
      end
    end
  end
  res
end

हमें दोहराव के साथ कुछ उदाहरण लेना चाहिए:

A = %W{1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 1 10 2 11 12 4 13 14 6 15 12 16 17 18 19}.map(&:to_i)

अब बेंचमार्क

puts "NAIVE 100 times:"
puts time_elapsed{
  100.times do
    naive(A)
  end
}

puts "rl 100 times"
puts time_elapsed{
  100.times do
    rightleft(A)
  end
}

परिणाम:

NAIVE 100 times:
[14, 30, 29, 53,...., 0, 0]
Time elapsed 485.935997 milliseconds

rl 100 times
[14, 30, 29, 53,...., 0, 0]
Time elapsed 81.735048 milliseconds

लेकिन जब आपके पास कोई पुनरावृत्ति नहीं है - यह अनुकूलन थोड़ा धीमा कर देगा। यहां संख्या 1,2,3 के परिणाम दिए गए हैं ... 99,100 शफल किए गए हैं:

NAIVE 100 times:
[70, 7,... 1, 0]
Time elapsed 99.58762899999999 milliseconds

rl 100 times
[70, 7, ... 1, 0]
Time elapsed 113.186392 milliseconds




language-agnostic