Задача по алгоритму У вас есть массив различных чисел и число x, которого нет в массиве. Напишите эффективный алгоритм, который вычисляет количество минимальных элементов, которые необходимо добавить в массив, таким образом, чтобы медиана нового массива была равна x.
Например, если массив равен [10,15,3,8,11,4] и x=7, то нам нужно добавить по крайней мере 2 числа (например, 5,7), чтобы новая медиана была равна 7. Какова временная сложность вашего алгоритма?
(You have an array of different numbers and a number x which is not in the array. Write an efficient algorithm that computes the number of minimal elements one must add to the array such that the median of the new array will be x.
For example, if the array is [10,15,3,8,11,4] and x=7, then we need to add at least 2 numbers (e.g., 5,7) that the new median will be 7. What is the time complexity of your algorithm?)
Задача по алгоритму У вас есть массив различных чисел и число x, которого нет в массиве. Напишите эффективный алгоритм, который вычисляет количество минимальных элементов, которые необходимо добавить в массив, таким образом, чтобы медиана нового массива была равна x.
Например, если массив равен [10,15,3,8,11,4] и x=7, то нам нужно добавить по крайней мере 2 числа (например, 5,7), чтобы новая медиана была равна 7. Какова временная сложность вашего алгоритма?
(You have an array of different numbers and a number x which is not in the array. Write an efficient algorithm that computes the number of minimal elements one must add to the array such that the median of the new array will be x.
For example, if the array is [10,15,3,8,11,4] and x=7, then we need to add at least 2 numbers (e.g., 5,7) that the new median will be 7. What is the time complexity of your algorithm?)
Например, если массив равен [10,15,3,8,11,4] и x=7, то нам нужно добавить по крайней мере 2 числа (например, 5,7), чтобы новая медиана была равна 7. Какова временная сложность вашего алгоритма?
(You have an array of different numbers and a number x which is not in the array. Write an efficient algorithm that computes the number of minimal elements one must add to the array such that the median of the new array will be x.
For example, if the array is [10,15,3,8,11,4] and x=7, then we need to add at least 2 numbers (e.g., 5,7) that the new median will be 7. What is the time complexity of your algorithm?)
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения этой задачи можно использовать следующий подход:
Отсортировать исходный массив.Найти медиану исходного массива - это будет элемент в середине после сортировки.Если x больше медианы, то нам нужно добавить x к массиву, пока не дойдем до элемента, который больше или равен x, и проверять изменится ли медиана. Если да, то останавливаемся и возвращаем количество добавленных элементов.Если x меньше медианы, то нужно добавить x к массиву до тех пор, пока не дойдем до элемента, который меньше или равен x, и проверять изменится ли медиана.Такой алгоритм будет иметь временную сложность O(n), где n - длина исходного массива, так как нам нужно будет пройтись только по элементам массива для нахождения необходимого количества элементов для добавления.