重新排列數組,使偶數位置大於奇數


難度級別 容易獎學金
經常問 亞馬遜 LinkedIn OYO房間 時代互聯網 百會
排列 改編 排序

問題陳述

假設您有一個整數數組。 問題“重新排列數組,使偶數位置大於奇數”要求重新排列數組,使得數組中偶數位置的元素應大於其前一個元素。

如果位置“ i”為奇數,則Arr [i-1] <= Arr [i]。

如果位置“ i”是偶數,則Arr [i-1]> = Arr [i]。

Arr[] = {1, 4, 5, 2, 7}
1 7 2 5 4

說明:偶數位置的每個元素都大於先前位置(即奇數位置)的元素。

算法

1. Traverse the array from 0 to n (length of the array).
    1. Check if the position is even or odd if it is even,
        2. If arr[i] is greater than the arr[i-1], then swap the array elements.
    2. Else, if arr[i] is smaller than the arr[i-1], then swap the array elements.
2. Print the array.

解釋

我們給了 整數 大批。 我們已要求重新安排 排列 這樣,偶數位置的元素應大於前一個元素。 請記住,在此我們將不考慮基於0的索引。 因此,數組的第一個元素將被視為處於奇數位置。 而第二個則處於偶數位置,依此類推。 這個想法是遍歷數組並檢查數組的奇數和偶數位置。 如前所述,不考慮基於0的索引位置。 因此,我們將從第0個位置選擇第一個元素,並假設它在一個奇數位置,因為它在第一個位置,而1是一個奇數。 更正式地說,我們在此問題中遵循基於1的索引。

我們要做的是,我們必須從位置1遍歷數組,並檢查該位置是否為偶數。 如果為true,則我們將檢查偶數定位的元素是否大於先前定位的元素。 如果為true,則交換值。 我們還可以檢查元素位置是否不奇數​​,這也可以工作。 然後檢查偶數位置元素是否大於先前的位置。

我們應該只記住幾件事,如果偶數位置的元素不大於存儲在當前元素偶數位置之前的位置的元素的值,那麼我們應該替換或交換這些值。 因此,它們可以按順序排列,就像偶數定位的元素大於先前定位的元素或僅位於奇數定位的元素。 最後,打印完成交換的陣列。

重新排列數組,使偶數位置大於奇數

推薦碼

C ++代碼重新排列數組,使偶數位置大於奇數

#include<iostream>

using namespace std;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void rearrangeEvenPositioned(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        if (i % 2 == 0)
        {
            if (arr[i] > arr[i - 1])
                swap(&arr[i - 1], &arr[i]);
        }
        else
        {
            if (arr[i] < arr[i - 1])
                swap(&arr[i - 1], &arr[i]);
        }
    }
}

int main()
{
    int arr[] = {1, 4, 5, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrangeEvenPositioned(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
1 5 2 7 4

Java代碼重新排列數組,使得偶數位置大於奇數

class rearrangeArray1
{
    public static void rearrangeEvenPositioned(int arr[], int n)
    {
        for (int i = 1; i < n; i++)
        {
            if (i % 2 == 0)
            {
                if (arr[i] > arr[i - 1])
                {
                    int temp=arr[i-1];
                    arr[i-1]=arr[i];
                    arr[i]=temp;
                }
            }
            else
            {
                if (arr[i] < arr[i - 1])
                {
                    int temp=arr[i-1];
                    arr[i-1]=arr[i];
                    arr[i]=temp;
                }
            }
        }
    }
    public static void main(String args[])
    {
        int arr[] = {1, 4, 5, 2, 7};
        int n = arr.length;
        rearrangeEvenPositioned(arr, n);
        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");

    }
}

1 5 2 7 4

複雜度分析

時間複雜度

上)  哪裡 “ N” 是數組中元素的數量。 我們只遍歷了可以線性時間複雜度完成的數組。

空間複雜度

該算法有 O(1) 空間複雜度。 該算法是就地方法,因此佔用恆定空間。 但是由於輸入,整個程​​序的空間複雜度為O(N)。