Базовая концепция одномерных массивов, решения типовых задач

Рассмотрим решения базовых задач на манипуляцию с массивом данных.
Дата:
Время чтения:
10 мин.
Категория:
dsa
Теги:
  • циклы
  • массивы

Оглавление статьи

  1. Вводная часть
  2. Максимальный элемент в массиве
  3. Второй максимальный и минимальный элемент
  4. Проверить отсортирован ли массив
  5. Удаление дубликатов из массива
  6. Повернуть массив влево на одну позицию
  7. Повернуть массив влево на N позиций
  8. Повернуть массив вправо на N позиций
  9. Переместить нули в конец массива
  10. Линейный поиск
  11. Объединение двух отсортированных массивов
  12. Пересечение двух отсортированных массивов
  13. Поиск пропущенного числа
  14. Максимальная последовательность в массиве
  15. Число с одним повторением
  16. Самый длинный подмассив с сумой k
  17. Повторения в массиве
  18. Поиск числа с большим и меньшим повторением
  19. Поиск двух чисел
  20. Сортироватьмассив с тремя числами
  21. Количество повторений числа
  22. Максимальная сумма подмассива
  23. Покупка продажа акции
  24. Чередование положительных и отрицательных чисел
  25. Лидирующие числа
  26. Самая длинная последовательность
  27. Подсчет подмассивов с заданной суммой

Вводная часть

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

Максимальный элемент в массиве

Решение задачи с нахождением максимального элемента в массиве.

Например: [3,2,1,5,2] => 5

JS
const arr = [3,2,1,5,2]
let max = arr[0]

for (let i = 0; i < arr.length; i++) {
  if (arr[i] > max) max = arr[i]
}

// Максимальный элемент: 5
console.log('Максимальный элемент:', max)

Второй максимальный и минимальный элемент

Решение задачи с нахождением второго по счету максимального и минимального элемента в массиве.

Например: [4,5,33,1,8,9,9,6,9,0] => [0,1], [33,9]

JS
const arr = [4,5,33,1,8,9,9,6,9,0]
const min = secondMin(arr)
const max = secondMax(arr)

// Минимальный: [0,1]
console.log('Минимальный:', min)

// Максимальный: [33,9]
console.log('Максимальный:', max)

function secondMin(arr) {
  let min = arr[0]
  let smin = arr[1]

  for (let i = 2; i < arr.length; i++) {
    if (arr[i] < min) {
      smin = min
      min = arr[i]
    } else if (arr[i] !== min && arr[i] < smin) {
      smin = arr[i]
    }
  }

  return [min, smin]
}

function secondMax(arr) {
  let max = arr[0]
  let smax = arr[1]

  for (let i = 2; i < arr.length; i++) {
    if (arr[i] > max) {
      smax = max
      max = arr[i]
    } else if (arr[i] !== max && arr[i] > smax) {
      smax = arr[i]
    }
  }

  return [max, smax]
}

Проверить отсортирован ли массив

Решение задачи с проверкой массива на отсортированность элементов.

Например: [1,2,3,4,5,6,7,8] => true

JS
const sort = [1,2,3,4,5,6,7,8]
const notSort = [1,2,5,3,6,4,8,7]

// true
console.log('Отсортированный массив:', isSort(sort))

// false
console.log('Не отсортированный массив:', isSort(notSort))

function isSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      return false
    }
  }

  return true
}

Удаление дубликатов из отсортированного массива

Решение задачи с удалением дубликатов из массива.

Например: [1,1,2,3,4,4,5,6,7,8] => [1,2,3,4,5,6,7,8]

JS
const arr = [1,1,2,3,4,4,5,6,7,8]
const uniq = []

for (let i = 0; i < arr.length; i++) {
  if (arr[i] !== uniq[uniq.length - 1]) {
    uniq.push(arr[i])
  }
}

// Уникальные числа: [1,2,3,4,5,6,7,8]
console.log('Уникальные числа:', uniq)

Повернуть массив влево на одну позицию

Решение задачи с поворотом массива на одну позицию влево.

Например: [1,2,3,4,5] => [2,3,4,5,1]

JS
const arr = [1,2,3,4,5]

for (let i = 0; i < arr.length - 1; i++) {
  const tmp = arr[i]
  arr[i] = arr[i + 1]
  arr[i + 1] = tmp
}

// Повернутый массив: [2,3,4,5,1]
console.log('Повернутый массив:', arr)

Повернуть массив влево на N позиций

Решение задачи с поворотом массива на N позицию влево.

Например: [1,2,3,4,5] 4 => [2,3,4,5,1]

JS
let n = 4
const arr = [1,2,3,4,5]

while (n > 0) {
  for (let i = 0; i < arr.length - 1; i++) {
    const tmp = arr[i]
    arr[i] = arr[i + 1]
    arr[i + 1] = tmp
  }

  n--
}

// Повернутый массив: [5,1,2,3,4]
console.log('Повернутый массив:', arr)

Повернуть массив вправо на N позиций

Решение задачи с поворотом массива на N позиций вправо.

Например: [1,2,3,4,5] 4 => [2,3,4,5,1]

JS
const arr = [1, 2, 3, 4, 5];
const n = 4;

const shiftedArr = [];

for (let i = 0; i < arr.length; i++) {
  const newIndex = (i + n) % arr.length
  shiftedArr[newIndex] = arr[i]
}

// Повернутый массив: [2,3,4,5,1]
console.log('Повернутый массив:', shiftedArr)

Переместить нули в конец массива

Решение задачи с перемещением нулей в конец массива.

Например: [0, 1, 0, 2, 3, 2, 0, 0, 4, 5, 1, 0] => [1,2,3,2,4,5,1,0,0,0,0,0]

JS
const arr = [0, 1, 0, 2, 3, 2, 0, 0, 4, 5, 1, 0]
const tmp = []

for (let i = 0; i < arr.length; i++) {
  if (arr[i] !== 0) {
    tmp.push(arr[i])
  }
}

let end = arr.length - tmp.length
for (let i = 0; i < end; i++) {
  tmp.push(0)
}

// Исходный массив: [0, 1, 0, 2, 3, 2, 0, 0, 4, 5, 1, 0]
console.log('Исходный массив:', arr)

// Новый массив: [1,2,3,2,4,5,1,0,0,0,0,0]
console.log('Новый массив', tmp)

Решение задачи с линейным поиском элемента в массиве.

Например: [1,6,7,3,8,2,4,0,5] 3 => 3

JS
const search = 3
const arr = [1,6,7,3,8,2,4,0,5]
let position = -1

for (let i = 0; i < arr.length; i++) {
  if (arr[i] === search) {
    position = i
    break
  }
}

console.log('Позиция найденного элемента:', position)
console.log('Найденный элемент:', arr[position])

Объединение двух отсортированных множеств

Решение задачи с объединением двух отсортированных множеств.

Например: [1,1,2,3,4,5,9] [2,3,4,4,5,6] => [1,2,3,4,5,9,6]

JS
const arr1 = [1,1,2,3,4,5,9]
const arr2 = [2,3,4,4,5,6]
const union = new Set()

for (let i = 0; i < arr1.length; i++) {
  union.add(arr1[i])
}

for (let i = 0; i < arr2.length; i++) {
  union.add(arr2[i])
}

const res = []
for (let item of union) {
  res.push(item)
}

// Объединенное множество: [1,2,3,4,5,9,6]
console.log('Объединенное множество:', res)

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

Решение задачи с пересечением двух отсортированных массивов.

Например: [1,2,2,3,3,4,5,6] [2,3,3,5,6,6,7] => [2,3,3,5,6]

JS
const arr1 = [1,2,2,3,3,4,5,6]
const arr2 = [2,3,3,5,6,6,7]
const visit = Array(Math.max(arr1.length, arr2.length)).fill(0)
const res = []

for (let i = 0; i < arr1.length; i++) {
  for (let j = 0; j < arr2.length; j++) {
    if (arr2[j] > arr1[i]) {
      break
    }

    if (arr1[i] === arr2[j] && visit[j] === 0) {
      res.push(arr1[i])
      visit[j] = 1
      break
    }
  }
}

// Пересеченный массив: [2,3,3,5,6]
console.log('Пересеченный массив:', res)

Вариант 2

JS
const arr1 = [1,2,2,3,3,4,5,6]
const arr2 = [2,3,3,5,6,6,7]
let i = 0
let j = 0
const res = []

while (i < arr1.length && j < arr2.length) {
  if (arr1[i] < arr2[j]) {
    i++
  } else if (arr2[j] < arr1[i]) {
    j++
  } else {
    res.push(arr1[i])
    i++
    j++
  }
}

// Пересеченный массив: [2,3,3,5,6]
console.log('Пересеченный массив:', res)

Поиск пропущенного числа

Решение задачи с поиском пропущенного числа.

Например: [1,2,3,4,5,7,8,10] => 6, 9

JS
const arr = [1,2,3,4,5,7,8,10]
let res = []

for (let i = 0; i < arr.length - 1; i++) {
  if (arr[i] + 1 !== arr[i + 1]) {
    res.push(arr[i] + 1)
  }
}

// Пропущенное число: [6, 9]
console.log('Пропущенное число:', res)

Вариант 2

JS
const arr = [1,2,3,4,5,6,7,8,10]
let xor1 = 0
let xor2 = 0

for (let i = 0; i < arr.length - 1; i++) {
  xor1 = xor1 ^ arr[i]
  xor2 = xor2 ^ (i + 1)
}

xor1 = xor1 ^ arr.length - 1

const res = xor1 ^ xor2

// Пропущенное число: 9
console.log('Пропущенное число:', res)

Максимальная последовательность в массиве

Решение задачи с поиском максимальной последовательностью в массиве.

Например: [1,1,0,1,1,1,0,1,1] => 3

JS
const arr = [1,1,0,1,1,1,0,1,1]
let count = 0
let max = 0

for (let i = 0; i < arr.length; i++) {
  if (arr[i] === 1) {
    count++
    max = Math.max(max, count)
  } else {
    count = 0
  }
}

// Максимальное число повторений: 3
console.log('Максимальное число повторений:', max)

Число с одним повторением

Решение задачи с поиском числа с одним повторением.

Например: [1,1,2,3,3,4,4] => 2

JS
let arr = [1,1,2,3,3,4,4]
let xorr = 0

for (let i = 0; i < arr.length; i++) {
  xorr ^= arr[i]
}

// Число с одним повторением: 2
console.log('Число с одним повторением:', xorr)

Самый длинный подмассив с сумой k

Решение задачи с поиском самого длинного подмассива с сумой k.

Например: [1,2,1,4,1,1,1,1,2,1,1,0,4] 3 => [1,1,1]

JS
const k = 3
const arr = [1,2,1,4,1,1,1,1,2,1,1,0,4]
const pos = Array(2).fill(0)

for (let i = 0; i < arr.length; i++) {
  let sum = arr[i]

  for (let j = i + 1; j < arr.length; j++) {
    sum += arr[j]

    if (sum === k && pos[1] < j - i + 1) {
      pos[0] = i
      pos[1] = j + 1
      break
    }
  }
}

// Самый длинный подмассив: [1,1,1]
console.log(arr.slice(pos[0], pos[1]))

Повторения в массиве

Рассмотрим решение задачи на подсчет повторяющихся элементов в массиве.

Например: [10,5,10,15,10,5] => [[10,3],[5,2],[15,1]]

JS
const arr = [10,5,10,15,10,5]

// Число/повторы: [[10,3],[5,2],[15,1]]
console.log('Число/повторы:', countFreq(arr))

function countFreq(arr) {
  const res = []
  let visited = []

  for (let i = 0; i < arr.length; i++) {
    if (visited[i] == true) continue

    let count = 0
    for (let j = i; j < arr.length; j++) {
      if (arr[i] == arr[j]) {
        visited[j] = true
        count++
      }
    }

    res.push([arr[i], count])
  }

  return res
}

Поиск числа с большим и меньшим повторением

Рассмотрим решение задачи на нахождение числа с большим и меньшим повторением в массиве.

Например: [10,5,10,15,10,5] => [10, 15]

JS
let arr = [10, 5, 10, 15, 10, 5]

// Больше/меньше повторений: [10, 15]
console.log('Больше/меньше повторений:', countFreq(arr))

function countFreq(arr) {
  let visited = []
  let maxFreq = 0
  let minFreq = arr.length
  let maxEle = 0
  let minEle = 0

  for (let i = 0; i < arr.length; i++) {

    if (visited[i] == true) continue

    let count = 0
    for (let j = i; j < arr.length; j++) {
      if (arr[i] == arr[j]) {
        visited[j] = true;
        count++;
      }
    }

    if (count > maxFreq) {
      maxEle = arr[i];
      maxFreq = count;
    }

    if (count < minFreq) {
      minEle = arr[i];
      minFreq = count;
    }
  }

  return [maxEle, minEle]
}

Поиск двух чисел

Рассмотрим решение задачи на нахождение двух чисел сумма которых равна заданному числу.

Например: [6,8,12,1,4,5,10] 18 => [6,12]

JS
const target = 18
const arr = [6,8,12,1,4,5,10]
let map = new Map()
let res = []

for (let i = 0; i < arr.length; i++) {
  const search = target - arr[i]

  map.set(search, arr[i])

  if (map.has(arr[i])) {
    res = [map.get(arr[i]), arr[i]]
    break
  }
}

// Сумма двух чисел: [6,12]
console.log('Сумма двух чисел:', res)

Вариант 2

JS
const target = 18
const arr = [6,8,12,1,4,5,10]
let left = 0
let right = arr.length -1
let res = []

arr.sort((a, b) => a - b)

while (left < right) {
  let sum = arr[left] + arr[right]

  if (sum === target) {
    res = [arr[left], arr[right]]
    break
  } else if (sum < target) {
    left++
  } else {
    right--
  }
}

// Сумма двух чисел: [6,12]
console.log('Сумма двух чисел:', res)

Сортировать массив с тремя числами

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

Например: [0,1,2,0,1,2,1,2,0,0,0,1] => [0,0,0,0,0,1,1,1,1,2,2,2]

JS
const arr = [0,1,2,0,1,2,1,2,0,0,0,1]
const res = []

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    if (arr[j] === i) {
      res.push(arr[j])
    }
  }
}

// Отсортированный массив: [0,0,0,0,0,1,1,1,1,2,2,2]
console.log('Отсортированный массив:', res)

Вариант 2

JS
const arr = [0,1,2,0,1,2,1,2,0,0,0,1]
let low = 0
let mid = 0
let high = arr.length - 1

while (mid <= high) {
  if (arr[mid] === 0) {
    const temp = arr[low]
    arr[low] = arr[mid]
    arr[mid] = temp

    low++
    mid++
  }

  else if (arr[mid] === 1) {
    mid++
  }

  else {
    const temp = arr[mid]
    arr[mid] = arr[high]
    arr[high] = temp

    high--
  }
}

// Отсортированный массив: [0,0,0,0,0,1,1,1,1,2,2,2]
console.log('Отсортированный массив:', arr)

Количество повторений числа

Рассмотрим решение задачи на поиск числа которое повторяется больше чем длина массива в два раза.

Например: [7,7,5,7,5,1,5,7,5,5,7,7,5,5,5,5] => 5

JS
const arr = [7,7,5,7,5,1,5,7,5,5,7,7,5,5,5,5]
let count = 0
let el = null

for (let i = 0; i < arr.length; i++) {
  if (count === 0) {
    count = 1
    el = arr[i]
  }

  else if (arr[i] === el) {
    count++
  }

  else {
    count--
  }
}

count = 0
for (let item of arr) {
  if (item === el) count++
}

if (count <= arr.length / 2) {
  el = -1
}

// Наибольшее число: 5
console.log('Наибольшее число:', el)

Максимальная сумма подмассива

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

Например: [-2,1,-3,4,-1,2,1,-5,4] => 6

JS
const arr = [-2,1,-3,4,-1,2,1,-5,4]
let max = 0

for (let i = 0; i < arr.length; i++) {
  let sum = arr[i]

  for (let j = i + 1; j < arr.length; j++) {
    sum += arr[j]

    if (sum > max) {
      max = sum
    }
  }
}

// Максимальная сумма подмассива: 6
console.log('Максимальная сумма подмассива:', max)

Вариант 2

JS
const arr = [-2,1,-3,4,-1,2,1,-5,4]
let sum = 0
let max = 0

for (let item of arr) {
  sum += item
  max = Math.max(sum, max)

  if (sum < 0) {
    sum = 0
  }
}

console.log(max)

// Максимальная сумма подмассива: 6
console.log('Максимальная сумма подмассива:', max)

Покупка продажа акции

Рассмотрим решение задачи на нахождение максимальной прибыли от покупки и продажи акции.

Например: [7,1,5,3,6,4] => 5

JS
const arr = [7,1,5,3,6,4]
let sell = 0
let buy = 0

for (let i = 0; i < arr.length; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[j] - arr[i] > arr[buy] - arr[sell]) {
      sell = i
      buy = j
    }
  }
}

// Купил: 1
// Продал: 6
// Максимальная прибыль: 5
console.log('Купил:', arr[sell])
console.log('Продал:', arr[buy])
console.log('Максимальная прибыль:', arr[buy] - arr[sell])

Чередование положительных и отрицательных чисел

Рассмотрим решение задачи на формирование массива в котором положительные числа чередуются с отрицательными.

Например: [3,1,-2,-5,2,-4,3,6,7,8,9] => [3,-2,1,-5,2,-4,3,6,7]

JS
const arr = [3,1,-2,-5,2,-4,3,6,7,8,9]
const minus = []
const plus = []
const res = []

for (let i = 0; i < arr.length; i++) {
  if (arr[i] < 0) {
    minus.push(arr[i])
  } else {
    plus.push(arr[i])
  }
}

for (let i = 0; i < Math.ceil(arr.length / 2); i++) {
  if (plus[i]) res[2 * i] = plus[i]
  if (minus[i]) res[2 * i + 1] = minus[i]
}

// Чередующиеся числа: [3,-2,1,-5,2,-4,3,6,7]
console.log('Чередующиеся числа:', res.filter(item => item))

Вариант 2

JS
const arr = [3,1,-2,-5,2,-4,3, 6,7,8,9]
let posIndex = 0
let negIndex = 1
const res = Array(arr.length).fill(0)

for (let i = 0; i < arr.length; i++) {
  if (arr[i] < 0) {
    res[negIndex] = arr[i]
    negIndex += 2
  } else {
    res[posIndex] = arr[i]
    posIndex += 2
  }
}

// Чередующиеся числа: [3,-2,1,-5,2,-4,3,6,7]
console.log('Чередующиеся числа:', res.filter(item => item))

Лидирующие числа

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

Например: [10,22,12,3,0,6] => [22,12,6]

JS
const arr = [10,22,12,3,0,6]
const res = []

for(let i = 0; i < arr.length; i++) {
  let leader = true

  for(let j = i + 1; j < arr.length; j++) {
    if (arr[i] < arr[j]) {
      leader = false
      break
    }
  }

  if (leader) res.push(arr[i])
}

// Лидирующие числа: [22,12,6]
console.log('Лидирующие числа:', res)

Самая длинная последовательность

Рассмотрим решение задачи на поиск самой длинной последовательности чисел в массиве.

Например: [102,4,100,1,101,3,2,1,1,5] => 5

JS
let arr = [102,4,100,1,101,3,2,1,1,5]
let res = 0
let max = 1

arr.sort((a, b) => a - b)

arr = [... new Set(arr)]

for(let i = 0; i < arr.length - 1; i++) {
  if (arr[i] + 1 === arr[i + 1]) {
    max += 1
  } else {
    res = Math.max(res, max)
    max = 1
  }
}

// Самая длинная последовательность: 5
console.log('Самая длинная последовательность:', res)

Подсчет подмассивов с заданной суммой

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

Например: [1,2,2,3,-3,1,1,1,4,2,-3] 3 => 7

JS
const arr = [1,2,2,3,-3,1,1,1,4,2,-3]
const k = 3
let count = 0

for (let i = 0; i < arr.length; i++) {
  let sum = 0

  for (let j = i; j < arr.length; j++) {
    sum += arr[j]

    if (sum === k) count++
  }
}

// Количество подмассивов: 7
console.log('Количество подмассивов:', count)
Предыдущая статья Базовая концепция рекурсии, решения типовых задач Следующая статья Базовая концепция двумерных массивов, решения типовых задач