จัดเรียง Array ใหม่เช่น arr [i]> = arr [j] ถ้าฉันเป็นเลขคู่และ arr [i] <= arr [j] ถ้าฉันเป็นเลขคี่และ j <i  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ อะโดบี อเมซอน ข้อเท็จจริง Zoho
แถว

สมมติว่าคุณมีจำนวนเต็ม แถว. คำสั่งปัญหาขอให้จัดเรียงอาร์เรย์ใหม่ในลักษณะที่องค์ประกอบที่ตำแหน่งคู่ในอาร์เรย์ควรมีค่ามากกว่าองค์ประกอบทั้งหมดก่อนหน้านั้นและองค์ประกอบที่ตำแหน่งคี่ควรมีค่าน้อยกว่าองค์ประกอบที่อยู่ก่อนหน้านั้น

ตัวอย่าง  

อินพุต

arr [] = {1, 4, 6, 2, 4, 8, 9}

เอาท์พุต

4 6 4 8 2 9 1

คำอธิบาย

องค์ประกอบทั้งหมดที่ตำแหน่งคู่มีค่ามากกว่าองค์ประกอบทั้งหมดที่อยู่ก่อนหน้านั้นและองค์ประกอบที่ตำแหน่งคี่จะน้อยกว่าองค์ประกอบก่อนหน้า

ขั้นตอนวิธี  

  1. ตั้งค่า evenPosition เป็น n / 2
  2. ตั้งค่า oddPosition เป็น n - evenPosition
  3. สร้างอาร์เรย์ (ชั่วคราว)
  4. จัดเก็บองค์ประกอบทั้งหมดของอาร์เรย์ที่กำหนดไว้ในอาร์เรย์ชั่วคราวนี้
  5. จัดเรียงอาร์เรย์ชั่วคราว
  6. ตั้งค่า j เท่ากับ oddPosition -1
  7. คัดลอกอาร์เรย์ชั่วคราวไปยังอาร์เรย์ดั้งเดิม [j] ที่ตำแหน่งคู่ (อิงตามดัชนี) ของอาร์เรย์ที่กำหนดและลดค่า j ลง 1
  8. ตั้งค่า j เป็น oddPosition
  9. คัดลอกชั่วคราวไปยังอาร์เรย์เดิม [j] ที่ตำแหน่งคี่ (อิงตามดัชนี) ของอาร์เรย์ที่กำหนดและเพิ่มค่า j ด้วย 1
  10. พิมพ์อาร์เรย์เดิมเนื่องจากมีการอัปเดตในอาร์เรย์เดิม

คำอธิบาย  

ด้วยอาร์เรย์ของจำนวนเต็มงานของเราคือการจัดเรียงอาร์เรย์ใหม่ในลักษณะที่องค์ประกอบที่ตำแหน่งจำนวนคู่ควรมากกว่าองค์ประกอบทั้งหมดที่อยู่ก่อนหน้านั้น และองค์ประกอบที่ตำแหน่งจำนวนคี่ควรน้อยกว่าตัวเลขทั้งหมดที่มีอยู่ก่อนหน้านั้น เราจะเห็นในตัวอย่างว่าองค์ประกอบที่ตำแหน่งคู่มากกว่าตัวเลขทั้งหมดที่อยู่ก่อนหน้านั้น ในที่นี้เราไม่ได้ถือเป็นตัวเลขตามดัชนี องค์ประกอบที่ 0 ตำแหน่งควรถือว่าเป็น 1 ตำแหน่งที่เป็นเลขคี่ 1st ตำแหน่งของอาร์เรย์คือ 2 ตำแหน่งที่เท่ากันในที่นี้เราไม่ได้พิจารณาการสร้างดัชนีตามอาร์เรย์ในผลลัพธ์ของเราเราเริ่มจาก 1 เป็นเลขคี่ไปยังเลข n

ดูสิ่งนี้ด้วย
Subarray สูงสุด

ทำสำเนาอาร์เรย์เดิมลงในอาร์เรย์ชั่วคราวนับจำนวนตำแหน่งคู่และคี่ในอาร์เรย์ที่กำหนด จากนั้นเราจะจัดเรียงอาร์เรย์ตามลำดับที่เพิ่มขึ้น ตอนนี้อัปเดตองค์ประกอบของอาร์เรย์ที่ตำแหน่งคี่ (การจัดทำดัชนีที่ไม่ใช่อาร์เรย์) จากอาร์เรย์ชั่วคราวเป็นค่าที่ลดลงของ oddPosition - 1 ถึง 0

องค์ประกอบทั้งหมดจากครึ่งหนึ่งของอาร์เรย์ชั่วคราวจะถูกเก็บไว้ที่ตำแหน่งคี่ของอาร์เรย์เดิม ในทำนองเดียวกันเราจะจัดเก็บค่าส่วนที่เหลือของครึ่งหลังของอาร์เรย์ชั่วคราวจะถูกเก็บไว้ที่ตำแหน่งคู่ของอาร์เรย์เดิมในลักษณะนี้เราสามารถจัดเรียงอาร์เรย์ใหม่เพื่อให้องค์ประกอบในตำแหน่งที่เท่ากันมากขึ้นและองค์ประกอบที่คี่ ตำแหน่งที่องค์ประกอบคี่จะมีขนาดเล็กกว่าองค์ประกอบทั้งหมดก่อนหน้านั้นตามลำดับ

จัดเรียง Array ใหม่เช่น arr [i]> = arr [j] ถ้าฉันเป็นเลขคู่และ arr [i] <= arr [j] ถ้าฉันเป็นเลขคี่และ j <i

การดำเนินงาน  

โปรแกรม C ++

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeArrayEvenOdd(int arr[], int n)
{
    int evenPosition = n / 2;

    int oddPosition = n - evenPosition;

    int temporaryArray[n];

    for (int i = 0; i < n; i++)
        temporaryArray[i] = arr[i];

    sort(temporaryArray, temporaryArray + n);

    int j = oddPosition - 1;

    for (int i = 0; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j--;
    }

    j = oddPosition;

    for (int i = 1; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,4,6,2,4,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArrayEvenOdd(arr, n);
    printArray(arr,n);
    return 0;
}
4 6 4 8 2 9 1

โปรแกรม Java

import java.util.*;

class rearrangeArray
{
    public static void rearrangeArrayEvenOdd (int arr[], int n)
    {
        int evenPosition = n / 2;

        int oddPosition = n - evenPosition;

        int[] temporaryArray = new int [n];

        for (int i = 0; i < n; i++)
            temporaryArray[i] = arr[i];

        Arrays.sort(temporaryArray);
        int j = oddPosition - 1;

        for (int i = 0; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j--;
        }

        j = oddPosition;

        for (int i = 1; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j++;
        }
    }
    public static void printArray(int arr[], int n)
    {

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String argc[])
    {
        int[] arr = { 1,4,6,2,4,8,9};
        int size =arr.length;
        rearrangeArrayEvenOdd (arr, size);
        printArray(arr, size);

    }
}
4 6 4 8 2 9 1

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

O (n บันทึก n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ดูสิ่งนี้ด้วย
Triplets ที่ไม่ซ้ำกันทั้งหมดที่รวมเป็นมูลค่าที่กำหนด

ความซับซ้อนของอวกาศ

O (n)  ที่ไหน “ n”  คือจำนวนองค์ประกอบในอาร์เรย์