Линейный поиск

Классические задачи линейного поиска

Линейный поиск - способ поиска, когда перебираются все элементы.

Сложность линейного поиска - линейная, т.е. $O(N)$.

Обычно ищут "подходящий" элемент или "наиболее подходящий элемент".

Задача 1. Найти первое вхождение положительного числа.

Дана последовательность чисел длиной N. Найти первое (левое) вхождение положительного числа X в нее или вывести -1, если число X не встречалось.

Решение:

Сначала положим в ответ -1, затем будем перебирать все элементы. Если текущий элемент равен X и ответ равен -1, запишем в ответ текущую позицию.

public static int findx(int[] seq, int x) {
    int ans = -1;
    for (int i = 0; i < seq.length; i++) {
        if (ans == -1 && seq[i] == x) {
            ans = i;
        }
    }

    return ans;
}

Задача 2. Найти последнее вхождение положительного числа.

Дана последовательность чисел длиной N. Найти последнее (правое) вхождение положительного числа X в неё или вывести -1, если число X не встречалось.

Решение:

Сначала положим в ответ -1, затем будем перебирать все элементы. Если текущий элемент равен X - запишем в ответ текущую позицию (без проверки что текущая позиция равна -1).

public static int findx(int[] seq, int x) {
    int ans = -1;
    for (int i = 0; i < seq.length; i++) {
        if (seq[i] == x) {
            ans = i;
        }
    }

    return ans;
}

Задача 3. Найти максимальное число в последовательности.

Дана последовательность чисел длиной N (N>0). Найти максимальное число в последовательности.

Решение:

Сначала положим в ответ нулевой элемент последовательности (он точно существует, тк N>0), затем будем перебирать все элементы. Если текущий элемент больше ответа - запишем в ответ текущий элемент.

public static int findMax(int[] seq) {
    int ans = seq[0];
    for (int i = 1; i < seq.length; i++) {
        if (seq[i] > ans) {
            ans = seq[i];
        }
    }

    return ans;
}

Если условие допускает пустую последовательность то этот случай нужно обрабатывать отдельно через if.

Строки сравниваются по символьно и когда символы начинают отличаться можно сказать какая строка меньше или больше. Если строки длинные то сравнение будет идти долго, время равно длине строки.

Лексикографический порядок - это сравнение с учетом регистра. Алфавитный порядок - это сравннеие, как в словаре, без учета регистра.

Решение задачи не подойдет для строк, так как будет постоянно перезаписываться значение ans, а для строк это требует больше времени, строки могут быть длинные.

Нужно запоминать не значение, а индекс максимального элемента.

public static String findMax(String[] seq) {
    int ans = 0;
    for (int i = 1; i < seq.length; i++) {
        if (seq[i].compareTo(seq[ans]) == 0) {
            ans = i;
        }
    }

    return seq[ans];
}

Задача 4. Найти максимальное число в последовательности и второе по величине число.

Дана последовательность чисел длиной N (N>1). Найти максимальное число в последовательности и второе по величине число (такое, которое будет максимальным, если вычеркнуть из последовательности одно максимальное число).

Решение:

Заведем две переменные для первого и второго максимума. Возьмем первые два числа из последовательности и запишем большее из них в переменную для первого макисмума, а меньшее - для второго. Пройдем по всей последовательности. Если очередное число больше первого максимума, то запишем во второй макисмум значение первого, а в первый - текущее число. Если только больше второго, запишем текущее число во второй макисмум.

public static int[] findMax2(int[] seq) {
        int max1, max2;
        if (seq[0] > seq[1]) {
            max1 = seq[0];
            max2 = seq[1];
        } else {
            max1 = seq[1];
            max2 = seq[0];
        }
        for (int i = 2; i < seq.length; i++) {
            if (seq[i] > max1) {
                max2 = max1;
                max1 = seq[i];
            } else if (seq[i] > max2) {
                max2 = seq[i];
            }
        }
        return new int[]{max1, max2};
    }

Задача 5. Найти минимальное четное число в последовательности.

Дана последовательность чисел длиной N. Найти минимальное четное число в последовательности или вывести -1, если такого не существует.

Решение:

В переменную для ответа положим -1. Если очередное число четное, а ответ равен -1 или ответ больше текущего числа, то запишем в ответ текущее число.

Универсальный способ для решения это завести boolean переменную с признаком встречали ли мы четное число или нет. Изначально она равна fasle, а как встретили четное число делаем ее true.

public static int findMinEven(int[] seq) {
    int ans = 0;
    boolean isFound = false;

    for (int i = 0; i < seq.length; i++) {
        int now = seq[i];
        if (now % 2 == 0 && (!isFound || now < ans)) {
            ans = now;
            isFound = true;
        }
    }
    return ans;
}

Два прохода

Задача 6. Вывести все самые короткие слова через пробел.

Дана последовательность слов. Вывести все самые короткие слова через пробел.

Если решать задачу за один проход, то есть сохранять количество символов в строке и саму строку и при нахождении еще более меньшей обновлять ее, это будет медленно и будет лишняя память заниматься. Так как мы будем накапливать слова, и хороше если добавление слова будет занимать $O(1)$, но может быть и больше, если копировать сами объекты. В Java лучше использовать для этих целей StringBuilder или StringBuffer.

public static String shortWords(String[] words) {
    int minLength = words[0].length();
    for (String word : words) {
        if (word.length() < minLength) {
            minLength = word.length();
        }
    }

    StringBuilder ans = new StringBuilder();
    for (String word : words) {
        if (word.length() == minLength) {
            ans.append(word).append(" ");
        }
    }

    return ans.toString();
}

Задача 7. Определить, сколько блоков воды осталось после дождя в низинах острова.

Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр. Остров игрока представляет собой набор столбцов различной высоты, состоящий из блоков камня и окруженный морем. Над островом прошел сильный дождь, который затопил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень.

По ландшафту острова определить, скоолько блоков воды осталось после дождя в низинах острова.

Решение:

После того как вода нальется наш остров примет форму ступенек. Давайте найдем самый высокий столбик(вершину) и до этой вершины будут ступеньки на подъем, вся вода будет сливаться влево от вершины, а все что справа от вершины будет утекать вправо.

Разделим задачу на две задачи по вершине острова и решим сначала для левой а потом по аналогии для правой.

Будем идти и запоминать максимальную высоту столбика который нам встретился, если следующий столбик меньше то добавляем разность высот между этими столбиками которая зальется водой, если же произошло обновление максимума, то количество воды не добавляем.

public static int isleFlood(int[] h) {
    int maxPos = 0;
    for (int i = 0; i < h.length; i++) {
        if (h[i] > h[maxPos]) {
            maxPos = i;
        }
    }

    int ans = 0;
    int nowMax = 0;
    for (int i = 0; i < maxPos; i++) {
        if (h[i] > nowMax) {
            nowMax = h[i];
        }
        ans += nowMax - h[i];
    }

    nowMax = 0;
    for (int i = h.length - 1; i > maxPos; i--) {
        if (h[i] > nowMax) {
            nowMax = h[i];
        }
        ans += nowMax - h[i];
    }
    return ans;
}

Задача с собеседования

Задача 8 - RLE

Дана строка (возможно пустая), состоящая из букв A-Z: AAAABBBCCХYZDDDВEEEFFFAAAAAABBBBBBBBBBBBBBBBBB} Нужно написать функцию RLE, которая на выходе даст строку вида: A4B3C2XYZD4E3F3F3A6B18. И сгенерирует ошибку если на вход пришла невалидная строка.

Если символ встречался один раз, он остается без изменений; Если символ повторяется более 1 раза, к нему добавляется количество повторений.

Попробуем упростить задачу и написать сначала функцию которая выдаст в ответе строку ABCXYZDEFAB.
Кладем изначально в переменную значение первого символа, далее проходим по всей строки и проверяем если символ не соответсвует предыдущему то добавляем предыдущий символ и обновляем его. В конце добавляем оставшийся последний символ.

public static String easyPeasy(String s){
    StringBuilder ans = new StringBuilder();
    char lastCh = s.charAt(0);
    for (int i = 1; i < s.length(); i++) {
        if(s.charAt(i) != lastCh){
            ans.append(lastCh);
            lastCh = s.charAt(i);
        }
    }
    ans.append(lastCh);

    return ans.toString();
}

Для полноценного выполнения задачи чтобы посчитать сколько раз символ подряд встретился в строке нужно добавить разность между последней позицией текщего повторяющегося символа и позицией последнего отличающегося символа. Добавим анонимную функцию для вычисления.

public static String rle(String s) {
    StringBuilder ans = new StringBuilder();
    int lastPos = 0;
    char lastCh = s.charAt(0);

    BiFunction<StringBuilder, Integer, StringBuilder> pack =
            (str, cnt) -> {
                if (cnt > 1) {
                    return str.append(cnt);
                }
                return str;
            };

    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) != lastCh) {
            ans.append(lastCh);
            pack.apply(ans, i - lastPos);
            lastCh = s.charAt(i);
            lastPos = i;
        }
    }

    ans.append(lastCh);
    pack.apply(ans, s.length() - lastPos);

    return ans.toString();
}

Вопросы

1. Алгоритмы линейного поиска это про алгоритмы Рабина Карпа? Алгоритм Рабина Карпа - это алгоритм поиска подстроки в строке и его с большой натяжкой можно назвать алгоритмом линейного поиска. Это довольно умный алгоритм.

2. Волнует ли вопрос оптимизации в алгоритме линейного поиска? Да, волнует, но бывают такие последовательности которые не обладают никаким свойством и задачи поиска максимума или поиска значения в последовательности про которую ничего не известно, никак быстрее не сделать мы так или иначе должны посмотреть каждое значение.