Введение в массивы — учебные пособия по структуре данных и алгоритмам

Опубликовано: 12 Декабря, 2022

Что такое массив?

An array is a collection of items of the same variable type stored that are stored at contiguous memory locations. It’s one of the most popular and simple data structures and is often used to implement other data structures. Each item in an array is indexed starting with 0.

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

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

Основные термины массива

  • Индекс массива: в массиве элементы идентифицируются по их индексам. Индекс массива начинается с 0.
  • Элемент массива: Элементы — это элементы, хранящиеся в массиве, доступ к которым можно получить по их индексу.
  • Длина массива: длина массива определяется количеством элементов, которые он может содержать.

Представление массива

Представление массива может быть определено его объявлением. Объявление означает выделение памяти для массива заданного размера.

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

C++




int arr[5];        // This array will store integer type element
char arr[10];    // This array will store char type element
float arr[20];  // This array will store float type element

C




int arr[5];        // This array will store integer type element
char arr[10];    // This array will store char type element
float arr[20];  // This array will store float type element

Java




/* Static Arrays are arrays that are declared before runtime
and are assigned values while writing the code.
*/
 
// The syntax of declaring a static array is:
<data type><variable name>[]
    = {<data1>, <data2>,…..<dataN> };
 
// Example:
int arr[] = { 2, 5, 6, 9, 7, 4, 3 };

C#




int[] arr = new int[5]; // This array will store integer type element

Javascript




// JS code
let arr=[10,20,30];  // This array will store integer
let arr2 = ["c", "d", "e"] // This array will store characters
let arr3 = [28.5, 36.5, 40.2] // This array will store floating elements

Python




# Python code
arr = [10, 20, 30# This array will store integer
arr2 = ["c", "d", "e"# This array will store characters
arr3 = [28.5, 36.5, 40.2# This array will store floating elements

Однако приведенное выше объявление является статическим или выделением памяти во время компиляции , что означает, что память элемента массива выделяется при компиляции программы. Здесь для хранения будет выделен только фиксированный размер (т.е. размер, который указан в квадратных скобках [] ) памяти, но не думаете ли вы, что это не будет такая же ситуация, как мы знаем размер массива каждый раз может быть случай, когда мы не знаем размер массива. Если мы объявим больший размер и сохраним меньшее количество элементов, это приведет к потере памяти или в случае, когда мы объявим меньший размер, у нас не будет достаточно памяти для хранения остальных элементов. В таких случаях выделение статической памяти нежелательно.

Можно ли создать динамический массив?

Ответ: Да . Возможно динамическое выделение памяти. Итак, динамическое выделение памяти — это процесс выделения пространства памяти во время выполнения или во время выполнения.

Ниже приведены языки, поддерживающие динамическое выделение памяти:

C++




int *array = new int[5];

Java




// The syntax of declaring a dynamic array is:
 
// <data type> <variable name> [ <Total Number of elements to be stored in array>];
// Example:
int arr[10]; // Store integer elements
String arr[5]; // Store String type of elements

Python3




# list of integers
my_list = [1, 2, 3, 4]
 
# Empty list
my_list = []
 
# list of mixed data types
my_list = ["Hello", 1, 5.5]

C#




int[] numArray = new int[] {};

Javascript




// JavaScript has dynamic arrays: their size is not predetermined, nor the type of data.
 
 // Create array using literal
var x = ["a", "b", "c"];  
 
// Create array using constructor
var x = new Array();       
 
// Create array using constructor with items
var y = new Array("a", "b", "c");

PHP




$arr = array("a","b","c");

Зачем нужны структуры данных массива?

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

Это означает, что мы можем использовать обычные переменные (v1, v2, v3, ..), когда у нас есть небольшое количество объектов. Но если мы хотим хранить большое количество экземпляров, становится сложно управлять ими с помощью обычных переменных. Идея массива состоит в том, чтобы представить множество экземпляров в одной переменной .

Типы массивов:

В основном есть два типа массивов:

  • Одномерный массив (одномерные массивы) . Вы можете представить одномерный массив в виде строки, в которой элементы хранятся один за другим.
  • Двумерный массив: двумерные многомерные массивы можно рассматривать как массив массивов или как матрицу, состоящую из строк и столбцов.
  • Трехмерный массив. Трехмерный многомерный массив содержит три измерения, поэтому его можно рассматривать как массив двумерных массивов.

Типы операций с массивами:

  • Обход: обход элементов массива.
  • Вставка: вставка нового элемента в массив.
  • Удаление: Удаление элемента из массива.
  • Поиск: поиск элемента в массиве.
  • Сортировка: поддержание порядка элементов в массиве.

Преимущества использования массивов :

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

Недостатки массива :

  • Поскольку массивы имеют фиксированный размер, после того, как им выделена память, ее нельзя увеличить или уменьшить, что делает невозможным хранение дополнительных данных, если это необходимо. Массив фиксированного размера называется статическим массивом.
  • Выделение меньшего объема памяти, чем требуется для массива, приводит к потере данных.
    Массив однороден по своей природе, поэтому в одном массиве не могут храниться значения разных типов данных.
  • Массивы хранят данные в смежных ячейках памяти, что делает удаление и вставку очень сложными для реализации. Эта проблема решается путем реализации связанных списков, которые обеспечивают произвольный доступ к элементам.

Применение массива :

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

Главные теоретические вопросы на собеседовании

С.но

Вопрос

Отвечать

1 Что произойдет, если вы не инициализируете массив? Вид
2 Почему сложность извлечения значения из массива составляет O (1) Вид
3 Когда следует использовать массив вместо списка? Вид
4 Что такое циклически отсортированный массив? Вид
5 Сравнение двух массивов с использованием hashmap? Вид
6 «Каковы преимущества связного списка перед массивом? В каких сценариях
мы используем LinkedList, а когда Array?»
Вид
7 Как перебирать строки и столбцы многомерного массива? Вид
8 Что подразумевается под разреженным массивом? Вид
9 Каковы преимущества кучи перед отсортированными массивами? Вид
10 Есть ли разница между int[] a и int a[]? Вид
11 Можем ли мы объявить размер массива как отрицательное число? Вид
12 Мы знаем, что массивы — это объекты, так почему мы не можем написать strArray.length()? Вид
13 Каковы преимущества отсортированных массивов? Вид
14 Что определяет размерность массива? Вид
15 Как проверить массив содержит значение или нет? Вид
16 Как создать массив/список внутри другого массива/списка? Вид
17 Как получить наибольшее и наименьшее число в массиве? Вид
18 Как я могу вернуть координаты/индексы строки в многомерном массиве? Вид
19 Как удалить объекты из массива в Java? Вид
20 Как C размещает элементы данных в многомерном массиве? Вид
21 Получить соседние элементы в двумерном массиве? Вид
22 C++ Как использовать и передавать трехмерный массив символов? Вид
23 Анонимный массив в Java Вид
24 Каково значение массива по умолчанию в Java? Вид
25 Как скопировать массив в другой массив? Вид
26 Как перебрать массив в java? Вид
27 Как объединить два отсортированных массива в отсортированный массив? Вид
28 Можем ли мы сделать массив изменчивым в Java? Вид
29 Какова логика реверсирования массива? Вид
30 Как получить индекс элемента массива? Вид
31 Можем ли мы расширить массив после инициализации? Вид
32 Как заполнить элементы (сразу инициализировать) в массиве? Вид
33 Разница между массивом и строкой в Java Вид
34 Вывести все подмассивы с нулевой суммой Вид
35 Индекс равновесия массива Вид
36 Как проверить массив содержит значение или нет? Вид
37 Как получить два верхних числа из массива? Вид
38 Как реализовать 3 стека с одним массивом? Вид

Топ 50 вопросов по кодированию на собеседовании

Простые задачи на массивы

С.но

Вопрос

Статья

Упражняться

1 Напишите программу, переворачивающую массив Вид Решать
2 Найдите минимальный и максимальный элемент в массиве Вид Решать
3 Пиковый элемент Вид Решать
4 Напишите программу для сортировки заданного массива Вид Решать
5 Найдите K-е наибольшее и K-е наименьшее число в массиве Вид Решать
6 Найти вхождение целого числа в массив Вид Решать
7 Сортировка массива 0, 1 и 2 Вид Решать
8 Подмассив с заданной суммой Вид Решать
9 Переместите все отрицательные элементы в одну сторону массива Вид Решать
10 Найдите объединение и пересечение двух отсортированных массивов. Вид Решать

Средние проблемы с массивами

С.но

Вопрос

Статья

Упражняться

1 Напишите программу для циклического поворота массива на единицу Вид Решать
2 Найдите пропущенное целое число Вид Решать
3 Подсчет пар с заданной суммой Вид Решать
4 Найти дубликаты в массиве Вид Решать
5 Сортировка массива с использованием алгоритма быстрой сортировки Вид Решать
6 Найдите общие элементы в трех отсортированных массивах Вид Решать
7 Найдите первый повторяющийся элемент в массиве целых чисел Вид Решать
8 Найти первый неповторяющийся элемент в заданном массиве целых чисел Вид Решать
9 Подмассивы с равными 1 и 0 Вид Решать
10 Перестройте массив, чередуя положительные и отрицательные элементы. Вид Решать
11 Найдите, существует ли какой-либо подмассив с суммой, равной нулю Вид Решать
12 Найдите наибольшую сумму смежных подмассивов Вид Решать
13 Найдите факториал большого числа Вид Решать
14 Найдите подмассив максимального продукта Вид Решать
15 Найдите самую длинную последовательную подпоследовательность Вид Решать
16 Найдите минимальный элемент в повернутом и отсортированном массиве Вид Решать
17 Максимальная сумма в конфигурации Вид Решать
18 Минимальные платформы Вид Решать
19 Минимизируйте максимальную разницу между высотами Вид Решать
20 Минимальное количество прыжков, чтобы добраться до конца Вид Решать
21 Проблема с запасом Вид Решать
23 Найдите тройку, которая суммируется с заданным значением Вид Решать
23 Наименьшее положительное пропущенное число Вид Решать
24 Найдите строку с максимальным количеством единиц Вид Решать
25 Распечатайте матрицу по спирали Вид Решать
26 Найти, является ли массив подмножеством другого массива Вид Решать
27 Реализовать два стека в массиве Вид Решать
28 Элемент большинства Вид Решать
29 Волновой массив Вид Решать
30 Улавливание дождевой воды Вид Решать

Сложные проблемы

С.но

Вопрос

Статья

Упражняться

1 Максимальный индекс Вид Решать
2 Путь максимальной суммы в двух массивах Вид Решать
3 Найдите пропущенные и повторяющиеся Вид Решать
4 Проблема покупки и продажи акций Вид Решать
5 Пара с заданной суммой в отсортированном массиве Вид Решать
6 Проблема распределения шоколада Вид Решать
7 Раздел равной суммы подмножества Вид Решать
8 Наименьшее положительное целое число, которое не может быть представлено в виде суммы Вид Решать
9 Проблема с раздачей монет Вид Решать
10 Самая длинная чередующаяся подпоследовательность Вид Решать

Часто задаваемые вопросы (FAQ) о массивах

1. Что такое массив в структуре данных на примере?

Массив — это набор элементов данных одного типа, хранящихся в смежных ячейках памяти. Бывший. интервал [5] = {1,2,3,4,5};

2. Почему массив — это структура данных?

Массивы хранят элементы одного типа, они классифицируются как однородные структуры данных. Они могут хранить числа, строки, символы, логические значения (true и false), объекты и т.д.

3. Какой структурой данных является массив?

Массив — это линейная структура данных , в которой одинаковые элементы хранятся в смежных ячейках памяти.

4. Какие есть типы массивов?

В основном есть два типа массивов:

  • Одномерный массив
  • Многомерный массив

5. Как данные хранятся в массиве?

Массив представляет собой набор элементов одного типа данных, хранящихся в смежных ячейках памяти, или говорит, что элементы хранятся в памяти один за другим. Массив использует систему индексов, начинающуюся с 0 и заканчивающуюся (n-1) , где n — его размер.

6. Разница между массивом и структурой?

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

7. Каковы ограничения массива?

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

8. Каковы преимущества массива?

Структура данных массива имеет множество преимуществ, и некоторые из них:

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

9. Какова цель использования массивов?

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

10. Что такое многомерный массив?

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

Вывод

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

Статьи по Теме:

  • Как начать изучение данных DSA?
  • Соревновательное программирование — полное руководство
  • Как легко освоить структуры данных и алгоритмы?
  • Почему важно изучать структуры данных и алгоритмы?
  • 15 лучших веб-сайтов для соревнований и соревнований по программированию
  • SDE SHEET — Полное руководство по подготовке к SDE
  • Amazon SDE Sheet — руководство по подготовке к интервью Amazon SDE
  • Подготовка к собеседованию в Google для инженера-программиста — полное руководство
  • 100 дней кода — полное руко