algorithm
स्लाइडिंग विंडो एल्गोरिथम

स्लाइडिंग विंडो एल्गोरिथम बेसिक जानकारी

स्लाइडिंग विंडो एल्गोरिथ्म का उपयोग दिए गए बड़े बफर या सरणी के विशिष्ट विंडो आकार पर आवश्यक संचालन करने के लिए किया जाता है। विंडो 1 तत्व से शुरू होती है और एक तत्व द्वारा सही स्थानांतरित होती रहती है। इसका उद्देश्य प्रत्येक विंडो में मौजूद न्यूनतम k संख्याओं का पता लगाना है। यह आमतौर पर स्लाइडिंग विंडो समस्या या एल्गोरिथ्म के रूप में जाना जाता है।

उदाहरण के लिए दिए गए सरणी में प्रत्येक n तत्व से अधिकतम या न्यूनतम तत्व को खोजने के लिए, खिड़की के एल्गोरिथ्म का उपयोग किया जाता है।

उदाहरण:

इनपुट ऐरे: [१ ३ -1 -3 ५ ३ ३ ६ 1]

खिड़की का आकार: 3

इनपुट सरणी के प्रत्येक 3 तत्व से अधिकतम तत्व:

+---------------------------------+---------+
|      Windows Position           |   Max   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |    3    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |    3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |    5    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |    5    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    6    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    7    |
+---+---+----+----+---+-----------+---------+

इनपुट ऐरे के प्रत्येक 3 तत्व से न्यूनतम तत्व:

+---------------------------------+---------+
|      Windows Position           |   Min   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |   -1    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |   -3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |   -3    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |   -3    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    3    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    3    |
+---+---+----+----+---+-----------+---------+

3 तत्व का योग खोजने के तरीके:

विधि 1:

पहला तरीका त्वरित सॉर्ट का उपयोग करना है, जब धुरी Kth स्थिति पर है, दाईं ओर के सभी तत्व धुरी से अधिक हैं, इसलिए, बाईं ओर के सभी तत्व स्वचालित रूप से दिए गए सरणी के सबसे छोटे तत्व बन जाते हैं।

विधि 2:

K तत्वों की एक सरणी रखें, इसे दिए गए इनपुट सरणी के पहले K तत्वों से भरें। अब K + 1 तत्व से, जांचें कि क्या वर्तमान तत्व सहायक सरणी में अधिकतम तत्व से कम है, यदि हां, तो इस तत्व को सरणी में जोड़ें। केवल उपरोक्त समाधान के साथ समस्या यह है कि हमें अधिकतम तत्व का ट्रैक रखने की आवश्यकता है। फिर भी काम करने योग्य। हम पूर्णांक के सेट में अधिकतम तत्व का ट्रैक कैसे रख सकते हैं? ढेर सोचो। मैक्स हीप सोचो।

विधि 3:

महान! O (1) में हम K तत्वों में से सबसे अधिक तत्व पहले से ही सबसे छोटे K तत्वों के रूप में चुनते हैं। यदि वर्तमान सेट में अधिकतम नव-माना तत्व से अधिक है, तो हमें K को सबसे छोटे तत्व के सेट में अधिकतम और नए तत्व को निकालने की आवश्यकता है। ढेर संपत्ति को बनाए रखने के लिए फिर से ढेर करें। अब हम आसानी से N के सरणी में K न्यूनतम तत्व प्राप्त कर सकते हैं।

अंतरिक्ष सहायक: O(n)

समय जटिलता: O(n)

C # में स्लाइडिंग विंडो एलगोरिदम का कार्यान्वयन

public class SlidingWindow
{
    public static int[] MaxSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var max = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] > max) max = input[i + j];
            }
            result[i] = max;
        }
        return result;
    }

    public static int[] MinSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var min = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] < min) min = input[i + j];
            }
            result[i] = min;
        }
        return result;
    }

    public static int[] MainMax(int[] input, int n)
    {
        return MaxSlidingWindow(input, n);
    }

    public static int[] MainMin(int[] input, int n)
    {
        return MinSlidingWindow(input, n);
    }
}