Вопросы с тегом «arrays»

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

62
Алгоритм на месте для перемежения массива

Вам дан массив из 2 н2n2n элементов a1,2, ... ,N, б1, б2, … БNa1,a2,…,an,b1,b2,…bna_1, a_2, \dots, a_n, b_1, b_2, \dots b_n Задача состоит в том, чтобы чередовать массив, используя алгоритм на месте так, чтобы результирующий массив был похож на б1,1, б2,2, … , БN,Nb1,a1,b2,a2,…,bn,anb_1, a_1, b_2,...

50
Хранение строкового секрета в (открытом) исходном коде

Я закончил разработку приложения для Android и собираюсь опубликовать его под лицензией GPL - я хочу, чтобы оно было с открытым исходным кодом. Однако природа приложения (игры) заключается в том, что оно задает загадки и кодирует ответы в строковом ресурсе. Я не могу опубликовать ответы! Мне...

34
Как измерить «сортировку»

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

31
Добавление элементов в отсортированный массив

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

22
Один элемент, который отличается двумя массивами. Как найти это эффективно?

Я готовлюсь к собеседованию по кодированию и не могу найти самый эффективный способ решения этой проблемы. Допустим, у нас есть два массива, состоящих из несортированных чисел. Массив 2 содержит число, которого нет в массиве 1. Оба массива имеют случайно расположенные числа, не обязательно в одном...

21
Существует ли алгоритм, который находит отсортированные подпоследовательности размера три за

Я хочу доказать или опровергнуть существование алгоритма, который, учитывая массив целых чисел, находит три индекса i , j и k такие, что i < j < k и A [ i ] < A [ j ] < A [ k ] (или находит, что такой тройки не существует) за линейное время.AAAя , джi,ji, jКkkя < J < Ki<j<ki...

20
Существует ли существующая структура данных фиксированного размера, которая вытеснит самый старый / последний элемент, если будет добавлен новый элемент?

Я ищу структуру данных, которая вытолкнет его самый старый / последний элемент, если новый элемент будет вставлен. Например, давайте Dпредставим структуру. Dсодержит 3 элемента типа Number Dзначения по умолчанию будут инициализированы в 1, 2и 3. D = [ 1 , 2 ,3 ]Dзнак равно[1,2,3]D = [1, 2, 3] Если...

19
Экономия на инициализации массива

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

16
Наибольшая сумма, делимая на n

Я задал этот вопрос на StackOverflow , но я думаю, что это более подходящее место. Это проблема из курса Введение в алгоритмы : У вас есть массив с положительными целыми числами (массив не нужно сортировать или элементы уникальны). Предложите алгоритм , чтобы найти наибольшую сумму элементов,...

15
Как найти 5 повторных значений в O (n) времени?

Предположим, у вас есть массив размером содержащий целые числа от до включительно, с ровно пятью повторениями. Мне нужно предложить алгоритм, который может найти повторяющиеся числа в времени. Я не могу ни о чем думать. Я думаю, что сортировка, в лучшем случае, будет ? Тогда при обходе массива...

15
Как реализовать два стека в одном массиве?

Я хочу начать с того, что это НЕ домашний вопрос. Я читаю Введение в алгоритмы - известный текст CLRS, чтобы стать лучшим программистом. Я пытаюсь решить проблемы и упражнения, приведенные в книге, самостоятельно. Я пытаюсь решить Excercise 10.1-2 из главы 10 «Элементарные структуры данных» из...

14
Почему отрицательные индексы массива имеют смысл?

Я наткнулся на странный опыт программирования на Си. Рассмотрим этот код: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Когда я компилирую и запускаю это, я не получаю никаких ошибок или предупреждений. Как сказал мой...

14
Подсчет пар инверсии

Классическое приложение «разделяй и властвуй» заключается в решении следующей проблемы: Учитывая массив различных сопоставимых элементов, подсчитайте количество пар инверсии в массиве: пар ( i , j ), таких что a [ i ] > a [ j ] и i < j .a[1…n]a[1…n]a[1\dots...

13
Переполнение безопасного суммирования

Предположим, мне дано целых чисел фиксированной ширины (т.е. они помещаются в регистр ширины ), , так что их сумма a 1 + a 2 + ⋯ + a n = S также помещается в регистр ширины ш .nnnwwwa1,a2,…ana1,a2,…ana_1, a_2, \dots a_na1+a2+⋯+an=Sa1+a2+⋯+an=Sa_1 + a_2 + \dots + a_n = Swww Мне кажется, что мы...

12
Подсчет количества сумм из смежных подмассивов массива

Нам дан массив со всеми a [ i ] > 0 .a [ 1 … n ]a[1…n]a[1 \ldots n]a [ i ] > 0a[i]>0a[i]>0 Теперь нам нужно найти сколько различных сумм могут быть сформирована из ее подрешеток (где подмассив представляет собой непрерывный диапазон массива, т.е. [ J ... K ] для некоторого J , к , сумма...

12
Поиск элемента, который встречается чаще всего в очень большом файле

Я слышал, что этот вопрос задавался много раз, и я надеялся получить какое-то мнение о том, какие могут быть хорошие ответы: у вас большой файл размером более 10 ГБ, и вы хотите выяснить, какой элемент встречается чаще всего, какой способ лучше сделать это? Итерация и отслеживание на карте,...

11
Предварительная обработка массива для подсчета элемента в срезе (сокращение до RMQ?)

Для массива натуральных чисел ≤ k , где k - константа, я хочу ответить на O ( 1 ) запросов вида: «сколько раз m появляется в массиве между индексами i и j "?a1,…,ana1,…,ana_1,\ldots,a_n≤k≤k\leq kkkkO(1)O(1)O(1)mmmiiijjj Массив должен быть предварительно обработан за линейное время. В частности, я...

11
Как обращаться с массивами во время корректных проверок в стиле Хоара

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

10
Название этой проблемы перестановки / сортировки?

Вам дан массив длины . Каждый элемент массива принадлежит одному из K классов. Вы должны переставить массив, используя минимальное количество операций подкачки, чтобы все элементы одного и того же класса всегда были сгруппированы вместе, то есть они образуют непрерывный подмассив. Например: NnnКKK...

9
Эффективное определение количества меньших элементов для каждого элемента в массиве

Я застрял на этой проблеме: Для заданного массива из первых натуральных чисел, произвольно переставленных, строится массив , так что - это число элементов от до которые меньше, чем , AAAnnnBBBB(k)B(k)B(k)A(1)A(1)A(1)A(k−1)A(k−1)A(k-1)A(k)A(k)A(k) я) Учитывая вы можете найти в времени? II) Учитывая...