Лучшие решения для задач Microsoft на собеседовании. Наибольший K такой, что в массиве существуют как K, так и -K.

Лучшие решения для задач Microsoft на собеседовании. Наибольший K такой, что в массиве существуют как K, так и -K.

Описание:

Напишите функцию, которая для массива A из N целых чисел возвращает наибольшее целое число K ›0, так что оба значения K и -K существуют в массиве A. Если такого целого числа нет, функция должна возвращать 0.

Пример 1:

Input: [3, 2, -2, 5, -3]
Output: 3

Пример 2:

Input: [1, 2, 3, -4]
Output: 0

Решение:

Эта задача очень проста. Это немного сложнее, чем найти максимальное значение в заданном массиве. Единственное, что нам нужно добавить, это проверить, содержит ли этот массив такое же значение с противоположной стороны от нуля. Другими словами, мы должны проверить все положительные значения в массиве и проверить, есть ли значения с таким же абсолютным значением, но с отрицательным знаком. Единственная структура данных, которая имеет постоянную сложность для доступа к несортированным элементам, это хеш-таблица.

Итак, сначала мы добавляем все заданные значения в хеш-таблицу.

Затем пройдите по всем элементам таблицы и проверьте, имеет ли положительный элемент такое же абсолютное значение, но с отрицательным знаком.

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

Код C ++:

int solution(const vector<int>& input){
    unordered_set<int> s(input.begin(),input.end());
    int max_value = 0;
    for(auto n : s){
        if((abs(n) > max_value) && (s.count(-n) != 0)) {
            max_value = n;
        }
    }
    return max_value;
}

Репозиторий с полной версией проекта вы можете найти здесь: https://github.com/jolly-fellow/microsoft/tree/master/largest_integer

Вернуться к оглавлению.