Знайти k-тий по порядку елемент у двох відсортованих масивах

Задача

Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти k-тий по порядку елемент.

Зробити це треба швидше ніж за лінійний час.

Рішення

Якщо просто мати по індексу на масив і пересувати їх на найменший елемент то усього нам знадобиться k ітерацій.

Так само якщо ми спробуємо злити масиви то не вдасться зробити це швидше ніж за лінійнипй час.

Якщо ж скористатися бінарним пошуком то загальна складність становитиме O(lg M + lg N), де M та N розміри вхідних масивів.

Робимо ми це так:

будуємо індекси i та j такі що i + j == k – 1. Наприклад ділимо відрізки навпіл.
якщо B[j-1] < A[i] < B[j] то A[j] є результатом пошуку
якщо A[i-1] < B[j] < A[i] то результатом буде B[j]
модифікуємо індекси таким чином:
1. якщо A[i] < B[j] то:
  1. якщо B[j] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в A
  2. інакше пересуваємо j на половину масиву вліво, і рівно на стільки ж позицій пересуваємо i (для того щоб їх сума дорівнювала k)
2. Робимо схожі перевірки:
  1. якщо A[i] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в B
  2. інакше пересуваємо i на половину масиву вліво, і рівно на стільки ж позицій пересуваємо j
повертаємося до кроку 2.

Код на gist:

Знайти підмасив з найбільшою сумою елементів

Задача

Дано масив цілих чисел. Треба знайти підмасив елементів з найбільшою сумою – тобто знайти і суму і індекси.

Додаткове зауваження. В принципі це доволі відома задача і в мережі можна знайти безліч рішень для неї, наприклад – http://sites.google.com/site/computationalthinking/kadanealgorithm, або http://www.algorithmist.com/index.php/Kadane’s_Algorithm. Але є одна річ на яку треба звернути увагу – усі елементи вхідного масиву можуть бути від’ємними. А цього якраз усі ті наведені реалізації і не враховують.

Тобто треба не лише в масиві { 10, –1, –1, 18, –20, 30 } знайти виділений підмасив, але і в такому як { –8, –2, –10 } знайти підмасив з одного елемента (-2).

Рішення

void find_the_biggest_subarray(
    int *a, size_t n, long int &sum, size_t &start, size_t &end)
{
    sum = LONG_MIN;
    size_t curStart = start = end = 0;
    if (!a || n == 0) return;

    long curSum = sum = a[0];
    
    for (size_t i = 1; i < n; ++i)
    {
        if (curSum < 0 && a[i] > curSum)
        {
            curSum = a[i];
            curStart = i;
        }
        else
        {
            curSum += a[i];
        }

        if (curSum > sum)
        {
            sum = curSum;
            start = curStart;
            end = i;
        }
    }
}

Знайти елемент що повторюється у масиві унікальних значень

Задача

У масиві з N елементів присутні усі елементи від 1 до N, але один з них продубльовано. Треба знайти цей елемент за лінійний час без використання додаткової пам’яті.

Рішення

Рішення полягає в тому щоб кожен елемент помістити в ту позицію в масиві яка дорівнює його значенню. Як тільки знайдемо елемент позиція якого вже зайнята таким самим значенням ми знайшли дублікат.

Для кожного елемента масиву з індексом і виконаємо наступні дії:

Беремо поточний елемент x = a[i]
Якщо x == i то збільшити і та повернитуся до кроку 1.
Якщо a[x] == x то ми знайшли елемент який дублюється, інакше обміняти місцями значення a[i] та a[x] і повернутися до кроку і.

int find_duplicated_item(int*a, size_t n) 
{ 
    int result =-1, x =0; 
    for (size_t i =0; i < n; ) 
    { 
        if (a[i] != i +1) 
        { 
            x = a[i]; 
            
            if (a[x] == x) 
            { 
                result = x; 
                break; 
            } 
            
            a[i] = a[x]; 
            a[x] = x; 
        } 
        else ++i; 
    } 
}

Нормалізувати рядок зі шляхом

Задача

У текстовому рядку вказано шлях до файлу чи директорії. В ньому можуть також зустрічатися дві крапки що позначають директорію на один рівень вгору. Треба прибати усі комбінації з двох крапок так щоб “/dir1/dir3” та “/dir1/dir2/../dir3/” стали ідентичними.

Рішення

Маабуть найпростішим буде рішення з вказівниками для читання та запису. Пересуваємо вказівник для читання доки не знайдемо послідовність “/../”. Далі пересуваємося від знайденої послідовності назад до першого попереднього символу “/” – це буде вказівник для запису.

Потім копіюємо рядок починаючи з позиції (вказвіник для читання + 3) у позицію (вказівник для запису). Після копіювання читання треба продовжити з тієї позиції в яку почали записувати (на випадок якщо у рядку є послідовності з більше ніж двох “..” послідовно).

int remove_double_dots(char *s)
{
    for (char *r = s; *r;)
    {
        if (r[0] == '/' && 
            r[1] == '.' && 
            r[2] == '.' && 
            (r[3] == '/' || r[3] == ''))
        {
            char *w = r - 1;
            for (; w >= s && *w != '/'; --w);
            
            if (w < s) return -1;

            char *p = w;

            r += 3;
            while (*w++ = *r++);
            r = p;
        }
        else
        {
            ++r;
        }
    }

    return 0;
}

У такого рішення є недолік – частини рядку постійно копіюються і при великій кількості “..” цей алгоритм буде неефективним.

Для покращення ми можемо зробити наступне. Кожного разу коли знаходимо у рядку символ “/” за яким йде звичайна директорія додаємо адресу цієї піддиректорії у спеціальний масив. Коли ж знаходимо послідовність “/../” то вилучаємо з масиву останній елемент і пропускаємо знайдену послідовність. Таким чином ми знаходимо адреси усих піддиректорій за один прохід.

Далі треба послідовно скопіювати усі піддиректорії з масиву у результуючий рядок.

int remove_double_dots_with_stack(char *s)
{
    size_t slashes = 0;
    for (char *p = s; *p; ++p)
    {
        if (*p == '/') ++slashes;
    }

    if (slashes == 0) return 0;

    std::vector<char*> words(slashes + 1);
    size_t word = 0;

    for (char *p = s; *p; )
    {
        if (*p == '/')
        {
            if (p[1] == '.' && 
                p[2] == '.' && 
                (p[3] == '/' || p[3] == ''))
            {
                if (word > 0)
                {
                    --word;
                    p += 3;
                }
                else
                {
                    return -1;
                }
            }
            else
            {
                words[word++] = ++p;
            }
        }
        else
        {
            ++p;
        }
    }

    char *w = s;
    for (size_t i = 0; i < word; ++i)
    {
        *w++ = '/';
        for (char *p = words[i]; *p && *p != '/'; ++p)
        {
            *w++ = *p;
        }
    }

    *w = '';

    return 0;
}

Чи є один рядок здвинутим іншим рядком

Задача

Треба визначити для двох рядків чи є один з них результатом циклічного зсуву символів іншого рядка.

Рішення

Якщо додати до першого рядка його копію то другий рядок має бути підрядком сумарного рядка, якщо звісно це ті ж самі рядки.

bool IsRotation(char *s1, char *s2)
{
    bool result = false;
    int l1 = strlen(s1), l2 = strlen(s2);
    if (l1 == l2 && l1 > 0)
    {
        char *s = new char[l1 * 2 + 1];

        strcpy(s, s1); // concat strings
        strcpy(s + l1, s1)

        result = strstr(s, s2) != NULL;
        delete []s;
    }

    return result;
}

Встановлення колонок і рядків в 0

Задача

Для масиву розміром MxN якщо будь-який елемент дорівнює 0 встановити всі елементи його рядка і колонки в 0.

Рішення

Головна проблема полягає в тому щоб при встановленні елементів у 0 не враховувати їх при подальшому пошуку. Інакше змінені елементи будуть можуть бути просканованим пізніше і призведуть до встановлення в 0 нових елементів.

Найпростішим рішенням буде створити копію матриці в якій і міняти елементи, а сканування проводити лише на оригінальній матриці.

Але насправді немає необхідності у всих MxN елементах – нам достатньо лише знати в яких рядках та стовпцях зустрівся хоча б один 0.

```
void SetZeroes(int* a, int n, int m)
```
```
{
```
```
    int *row = new int[m];
```
```
    int *col = new int[n];
```
```
    // scan elements
```
```
    for (int i = 0; i < n; ++i)
```
```
    {
```

        for (int j = 0; j < m; ++j)

```
        {
```

            if (a[i][j] == 0)

```
            {
```

                row[i] = 1;

                col[j] = 1;

```
            }
```
```
        }
```
```
    }
```
```
    // set elements
```
```
    for (int i = 0; i < n; ++i)
```
```
    {
```

        for (int j = 0; j < m; ++j)

```
        {
```

            if (row[i] == 1 || col[j] == 1)

```
            {
```

                a[i][j] = 0;

```
            }
```
```
        }
```
```
    }
```
```
    delete [] row;
```
```
    delete [] col;
```
```
}
```

* This source code was highlighted with Source Code Highlighter.