আমাদের একটি সর্ট করা অ্যারে দেওয়া আছে। এই অ্যারেটিকে সর্বোচ্চ, ন্যূনতম ফর্মে সাজাতে হবে, অর্থাৎ প্রথম উপাদান হবে সর্বোচ্চ উপাদান, দ্বিতীয় উপাদান হবে ন্যূনতম উপাদান, তৃতীয় উপাদান হবে ২য় সর্বোচ্চ উপাদান, চতুর্থ উপাদান হবে ২য় ন্যূনতম উপাদান, এবং এভাবেই চলবে। উদাহরণস্বরূপ:
Input : arr[ ] = { 10, 20, 30, 40, 50, 60 } Output : { 60, 10, 50, 20, 40, 30 } Explanation : অ্যারেটি { ১ম সর্বোচ্চ, ১ম ন্যূনতম, ২য় সর্বোচ্চ, ২য় ন্যূনতম, ৩য় সর্বোচ্চ, ৩য় ন্যূনতম } ফর্মে পুনর্বিন্যাস করা হয়েছে। Input : arr [ ] = { 15, 17, 19, 23, 36, 67, 69 } Output : { 69, 15, 67, 17, 36, 19, 23 }
একটি অ্যারেকে সর্বোচ্চ ও ন্যূনতম ফর্মে পুনর্বিন্যাস করার জন্য একক পদ্ধতি আছে।
সমাধানের পদ্ধতি
একটি অ্যারেকে সর্বোচ্চ ও ন্যূনতম ফর্মে পুনর্বিন্যাস করার জন্য একক পদ্ধতি আছে।
টু-পয়েন্টার পদ্ধতি
দুটি ভেরিয়েবল ব্যবহার করুন: min এবং max, যা যথাক্রমে ন্যূনতম ও সর্বোচ্চ উপাদানের দিকে নির্দেশ করবে। একই আকারের একটি নতুন খালি অ্যারে তৈরি করুন যাতে পুনর্বিন্যাস করা অ্যারেটি সংরক্ষণ করা যায়। এখন অ্যারেটির ওপর পুনরাবৃত্তি করুন। যদি বর্তমান সূচক জোড় (even) হয়, তবে arr[max] উপাদানটি নতুন অ্যারেতে যোগ করুন এবং max কে ১ কমিয়ে দিন। যদি সূচক বিজোড় (odd) হয়, তবে arr[min] উপাদানটি যোগ করুন এবং min কে ১ বাড়িয়ে দিন। এই প্রক্রিয়া तब तक চালিয়ে যান যতক্ষণ max, min থেকে ছোট হয় না।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main () { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); // পুনর্বিন্যাস করা অ্যারে সংরক্ষণের জন্য নতুন অ্যারে তৈরি int final[n]; // প্রাথমিক ও চূড়ান্ত উপাদানের সূচকে নির্দেশ করার ভেরিয়েবল int min = 0, max = n - 1; int count = 0; // max, min থেকে ছোট বা সমান না হওয়া পর্যন্ত লুপ চালান for (int i = 0; min <= max; i++) { // count জোড় হলে max সূচকের উপাদান সংরক্ষণ করুন if (count % 2 == 0) { final[i] = arr[max]; max--; } // count বিজোড় হলে min সূচকের উপাদান সংরক্ষণ করুন else { final[i] = arr[min]; min++; } count++; } // চূড়ান্ত পুনর্বিন্যাস করা অ্যারে প্রিন্ট করুন for (int i = 0; i < n; i++) cout << final[ i ] << " "; return 0; }
আউটপুট
6 1 5 2 4 3
উপরোক্ত কোডের ব্যাখ্যা
- ভেরিয়েবলগুলো min=0 এবং max = অ্যারের_দৈর্ঘ্য(n) - 1 হিসেবে আরম্ভ করা হয়েছে।
- for (int i = 0; min <= max; i++) লুপটি max, min থেকে বড় না হওয়া পর্যন্ত অ্যারেটির ওপর পুনরাবৃত্তি করে।
- যদি count বিজোড় হয়, তবে (max) উপাদানটি final অ্যারেতে যোগ করা হয় এবং max ভেরিয়েবলটি ১ কমায়।
- যদি count জোড় হয়, তবে (min) উপাদানটি final অ্যারেতে যোগ করা হয় এবং min ভেরিয়েবলটি ১ বাড়ায়।
- চূড়ান্ত ফলাফল final[ ] অ্যারেতে সংরক্ষিত থাকে।
উপসংহার
এই আর্টিকেলে, আমরা দেয়া অ্যারেটিকে max-min ফর্মে পুনর্বিন্যাস করার সমাধান নিয়ে আলোচনা করেছি। আমরা সমাধানের পদ্ধতি নিয়ে আলোচনা করেছি এবং O(n) সময় জটিলতায় একটি অপ্টিমাইজড সমাধান দিয়েছি। আমরা এর জন্য একটি C++ প্রোগ্রামও লিখেছি। একইভাবে, এই প্রোগ্রামটি C, Java, Python ইত্যাদি অন্য ভাষায়ও লিখা সম্ভব। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
