ओ (एन) समय

Question

में किसी सरणी के तत्व की आवृत्ति का आकलन करना मुझे लगता है कि शीर्षक थोड़ा भ्रामक हो सकता है, लेकिन मैं बेहतर नहीं सोच सकता था। मेरे पास एक सरणी ए [] है, लेकिन सभी जिनमें से एक तत्व कई बार होता है जो 15 का एक बहु है, उदा। 2 30 बार होता है, 3 45 बार होता है। लेकिन एक तत्व x बार होता है जहां x 15 का बहु नहीं होता है। मैं संख्या x कैसे मुद्रित करूं? मैं हैश-टेबल के बिना एक रैखिक समाधान की तलाश में हूं।

धन्यवाद।

Answer 1

स्टैक ओवरफ्लो पर, यहां एक ही सवाल था, लेकिन मुझे यह नहीं मिला।

चलिए 15 के बजाय 3 का उपयोग करते हैं, क्योंकि यह आसान होगा और मुझे लगता है कि यह पूरी तरह समतुल्य है। अनुक्रम 4, 5, 4, 5, 3, 3, 4, 5 होगा, बाइनरी 100, 101, 100, 101, 11, 11, 100, 101 में।

आप निम्न कर सकते हैं: योग सभी मूल्यों संख्या के कम से कम में महत्वपूर्ण बिट और (मूल रूप से 15) 3 से अधिक शेष ले:

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

अगर यह != 0 है तो उस बिट 1 के बराबर करने के लिए है संख्या जो हम खोजने की कोशिश कर रहे हैं। अब अगले करने के लिए ले जा सकते हैं:

bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0

bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0

तो हम bit3 == 0, bit2 != 0, bit1 != 0 है, 011 बना रही है। दशमलव में कनवर्ट करें: 3।

अंतरिक्ष जटिलता O(1) है और समय जटिलता O(n * BIT_LENGTH_OF_VARS), जहां BIT_LENGTH_OF_VARS == 8 बाइट के लिए, BIT_LENGTH_OF_VARS == 32 पूर्णांक, आदि तो यह बड़ा हो सकता है के लिए है, लेकिन स्थिरांक asymptotic व्यवहार को प्रभावित नहीं करते और O(n * BIT_LENGTH_OF_VARS) वास्तव में O(n) है।

यही है!