Преуредите низ тако да „арр [ј]“ постане „и“ ако је „арр [и]“ „ј“


Ниво тешкоће Лако
Често питани у амазонка Делхивери Кулиза Нагарро радити Тимес Интернет Иатра
Ред

Изјава о проблему

Проблем "Преуређивање низа тако да 'арр [ј]' постане 'и' ако је 'арр [и]' је 'ј'" наводи да имате „Н“ низ величине који садржи целе бројеве. Бројеви у низу су у опсегу од 0 до н-1. Изјава о проблему тражи да се низ преуреди на такав начин да низ [и] = ј постане арр [ј] = и.

Пример

arr[]={1,3,5,2,0,4}
4 0 3 1 5 2

Објашњење

арр [0] = 1 се мења у арр [1] = 0

арр [1] = 3 се мења у арр [3] = 1

арр [2] = 5 се мења у арр [5] = 2

арр [3] = 2 се мења у арр [2] = 3

арр [4] = 0 се мења у арр [0] = 4

арр [5] = 4 се мења у арр [4] = 5

па кад се штампа ⇒

арр [0] ⇒ арр [1] ⇒ арр [2] ⇒ арр [3] ⇒ арр [4] ⇒ арр [5]

КСНУМКС КСНУМКС КСНУМКС КСНУМКС КСНУМКС КСНУМКС

Алгоритам за преуређивање низа тако да „арр [ј]“ постаје „и“ ако је „арр [и]“ „ј“

1. Traverse the array from 0 to n-1(inclusively).
    1. Do arr [ arr % n ] + = i * n.
2. Then update the value of arr[ i ] =arr[ i ] / n.
3. Print the array.

Објашњење

С обзиром на поредак of интегерс. Бројеви које држи су у опсегу од 0 до н - 1. Преуредићемо бројеве низа пф. Тако да елементи у низу постану такви да је арр [ј] = и ако је арр [и] = ј. Дакле, то значи да ако имамо неку вредност на и-ој позицији као ј, тада ту вредност променимо у ј-ту позицију низа. Такође, дали смо елементе низа у опсегу од 0 до н-1. Дакле, број не може премашити дужину низа. Дакле, може бити корисно када прелазимо низ, можемо узети било коју вредност броја као индекс и извршити неке операције над њим.

Јер ћемо извршити неке операције на самом низу. Изабраћемо сваки елемент низа и пронаћи образац од арр [и]% н, где је н дужина низа. Као што смо раније поменули, бројеви су у опсегу од 0 до н-1. Дакле, када сазнамо модул било ког броја са н. Неће премашити број већи од индекса низа, јер ће се модул арр [и]% н поново третирати као индекс низа. А онда га складиштимо у множењу и * н. Ажурирајте сваку вредност модула као индекс низа и збројите га са собом.

Ово само радимо да бисмо сачували и ажурирали вредности у низу ако ћемо их преузети. Морамо их само поделити. Јер ако помножите број са к и поделите са к, број ће постати неутралан какав јесте. Ажурирајте арр [и] дељењем истог арр [и] са н и сачувајте га у арр [и]. На тај начин ћемо добити жељени резултат. То је начин како преуредити низ тако да 'арр [ј]' постане 'и' ако је 'арр [и]' 'ј'.

Преуредите низ тако да „арр [ј]“ постане „и“ ако је „арр [и]“ „ј“

код

Ц ++ код за преуређивање низа тако да „арр [ј]“ постане „и“ ако је „арр [и]“ „ј“

#include<iostream>

using namespace std;

void rearrangeIndexValue(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[arr[i] % n] += i * n;
    }

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

    cout << "Array after modifying :";
    rearrangeIndexValue(arr,n);
    printArray(arr, n);

    return 0;
}
Array after modifying :4 0 3 1 5 2

Јава код за преуређивање низа тако да 'арр [ј]' постане 'и' ако је 'арр [и]' 'ј'

class rearrangeArray2
{
    public static void rearrangeIndexValue(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[arr[i] % n] += i * n;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] /= n;
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,3,5,2,0,4};
        int n = arr.length;

        rearrangeIndexValue(arr, n);

        System.out.print("Array after modifying : ");
        printArray(arr, n);
    }
}
Array after modifying : 4 0 3 1 5 2

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Иако смо два пута прешли преко елемената низа. Дакле, ово се и даље рачуна само као линеарна временска сложеност.

Сложеност простора

Он) где „Н“ је број елемената у низу. Пошто нисмо ускладиштили ништа везано за сваки елемент и заузимали смо само константан простор. Дакле, сложеност простора алгоритма је константна.