M диапазонын ауыстырып қосу операцияларынан кейінгі екілік массив


Күрделілік дәрежесі орта
Жиі кіреді Amazon Coursera Голдман Сакс Google Сұр Оранж Snapchat
Array Сұрақ мәселесі

Сізге екілік массив берілген, ол бастапқыда 0 және Q сұраулар санынан тұрады. Проблемалық шешім мәндерді ауыстыруды сұрайды (0-ді 1-ге, ал 1-ді 0-ге айналдыру). Q сұраулары орындалғаннан кейін нәтижелік жиымды басып шығарыңыз.

мысал

arr[] = {0, 0, 0, 0, 0}

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

Түсіндіру

1-ауысу   0,1,1,1,0

2-ауысу 1,0,1,1,0

3-ауысу 1,0,0,0,1

M диапазонын ауыстырып қосу операцияларынан кейінгі екілік массив

Алгоритм

  1. N + 2 өлшемді буль массивін құрыңыз.
  2. Логикалық жиымды әр индекс үшін жалған етіп бастаңыз.
  3. Енді әрбір сұраныс үшін элементті солға және оңға + 1 индексімен аударыңыз.
  4. Енді массивті xor жиымының префиксі ретінде толтырыңыз. Барлық элементтердің xor-ін 1 индексінен i-ге дейін индексінде сақтаңыз.
  5. Массивті басып шығарыңыз

M диапазонын ауыстырып қосу операцияларынан кейінгі екілік массивке түсініктеме

Екілік берілген массив, 0-ден және 1-ден тұрады және аты айтып тұрғандай. Бірақ бастапқыда ол тек 0 мәндерін ғана қамтиды. Сұрақтардың Q санын ескере отырып. Әр сұрауда екі мән бар, мәндер диапазонның басталу нүктесі және диапазонның аяқталу нүктесі болып табылады, осы диапазондарда біз мәндерді ауыстыруымыз керек, егер ауыстыру 0-ді 1-ге, ал 1-ді 0-ге айналдыру керек болса Q саны ( сұрау саны) рет. Ол үшін біз а құрамыз Бульдік n + 2 жиымының ұзындығынан екі өлшемді массив. Содан кейін біз Q мәндерін бірнеше рет ауыстырамыз, егер сұраулардың саны көп болса, біз оны өзіміз деп атаудың қажеті жоқ, керісінше, біз цикл жасаймыз және оны әр түрлі сұраныс нөмірлерімен және кірістермен атаймыз.

Ауыстыру кезінде мәндерді дәл сол жиымдағы диапазон ретінде берілген дәл орындарда түрлендіріңіз, XOR әрекетін орындау арқылы барлық нөлдерді нольге, ал нөлге айналдырыңыз. XOR операциясы біз үшін дәл сол сандарды немесе мәндерді тапқан жағдайда жасайды, егер 0 мәнін береді, егер басқа мәндер санын тапса, жалған болады. Бұл 1-ді береді, нәтижесінде шындықты білдіреді. Сонымен, мәндерді төңкеру үшін ауыстырып қосу функциясында да осылай жасаймыз.

Массивті айналып өтіп, массивте операция жасаңыз. Массивтің ағымдағы және алдыңғы мәнінде XOR операциясын орындаңыз. Біз дәл сол битті тапқандай жасадық, әйтпесе 0 береді. Бұл әрекет ауқым ішіндегі барлық мәндерді ауыстыратын соңғы болады. Соңында массивті басып шығарыңыз.

код

M диапазонын ауыстырып қосу операцияларынан кейін екілік массив үшін C ++ жүйесінде жүзеге асыру

#include<iostream>

using namespace std;

void Toggle(bool arr[], int start, int end)
{
    arr[start] ^= 1;
    arr[end+1] ^= 1;
}

void getToggling(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}

void printOutput(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}

int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};

    Toggle(arr, 1, 5);
    Toggle(arr, 2, 5);
    Toggle(arr, 3, 5);

    getToggling(arr, n);

    printOutput(arr, n);
    return 0;
}
1 0 1 1 1

M диапазонын ауыстырып қосу операцияларынан кейін екілік массивке арналған Java-да енгізу

class ToggleArray
{
    static void Toggle(boolean arr[], int start, int end)
    {
        arr[start] ^= true;
        arr[end + 1] ^= true;
    }

    static void getToggling(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            arr[k] ^= arr[k - 1];
        }
    }

    static void printOutput(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            if(arr[k] == true)
                System.out.print("1" + " ");
            else
                System.out.print("0" + " ");
        }
    }

    public static void main(String args[])
    {
        int n = 5, m = 3;
        boolean arr[] = new boolean[n + 2];

        Toggle(arr, 1, 5);
        Toggle(arr, 2, 5);
        Toggle(arr, 3, 5);

        getToggling(arr, n);

        printOutput(arr, n);
    }
}
1 0 1 1 1

Күрделілікті талдау

Уақыттың күрделілігі

O (n + q) қайда «N» бұл массивтегі элементтер саны және “q”- бұл сұраулар саны. Барлық сұраулар O (1) уақытта орындалады, содан кейін жаңарту O (N) уақытты қажет етеді.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.