Kadane's algorithm
code
/**
* @param {number[]} arr - Array com valores arbitrários.
* @returns {number} O valor do subarray com maior soma em `arr`.
*/
function maxSubArrSum(arr) { // O(n) em tempo e O(1) em espaço
let maxSum = arr[0] || Number.MIN_VALUE;
let currSum = maxSum;
for (let i=1; i < arr.length; ++i) {
currSum = Math.max(arr[i], currSum + arr[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
maxSubArrSum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6
// \__________/
code
/**
* @param {any[]} arr - Array com valores arbitrários.
* @returns {any[]} O mesmo array `arr` mas com os itens (potencialmente)
* trocas de ordem de maneira aleatória.
*/
function shuffleInplace(arr) { // O(n) em tempo e O(1) em espaço
for (let i=items.length-1; i > 0; --i) {
const randomIdx = randomIntFromInterval(0, i)
const randomElem = arr[randomIdx]
// swap
arr[randomIdx] = arr[i]
arr[i] = randomElem
}
return arr;
}
function randomIntFromInterval(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min)
}
code
/**
* @param {number[]} nums - Array não vazio de inteiros,
* onde cada elemento aparece duas vezes, exceto um.
* @returns {number} O único elemento que não se repete em `nums`.
*/
function singleNumber(nums) { // O(n) em tempo e O(1) em espaço
let badNum = 0
for (const num of nums) badNum ^= num
return badNum
}
since:
- a XOR a = 0
- a XOR 0 = a
- (a XOR b) XOR c = a XOR b XOR c
code
/**
* @param {number[]} arr - Array ordenado em ordem crescente.
* @param {number} k - Elemento a ser procurado em `arr`.
* @returns {number} Quantidade de vezes em que `k` aparece em `arr`.
*/
function getOccurrencesOfK(arr, k) { // O(log n) em tempo; O(n) em espaço por ser recursivo
const firstOccurrence = binarySearch('FIRST', {
array: arr,
value: k,
start: 0,
end: arr.length-1,
})
if (firstOccurrence < 0) return 0
const lastOccurrence = binarySearch('LAST', {
array: arr,
value: k,
start: 0,
end: arr.length-1,
})
return lastOccurrence - firstOccurrence + 1
}
/**
* @param {'FIRST' | 'LAST'} kind
* @param {object} params
* @returns {number}
*/
function binarySearch(kind, { array, value, start, end }) {
if (array.length === 0 || start > end) return -1
/**
* @param {number} val
* @returns {boolean}
*/
const isInBounds = (val) => val < array.length
const mid = start + Math.floor((end - start)/2)
if (array[mid] === value) {
if (kind === 'FIRST') {
if (isInBounds(mid-1) && array[mid] === array[mid-1])
return binarySearch(kind, {
array,
value,
start: start,
end: mid-1,
})
}
if (kind === 'LAST') {
if (isInBounds(mid+1) && array[mid] === array[mid+1])
return binarySearch(kind, {
array,
value,
start: mid+1,
end: end,
})
}
return mid
} else if (array[mid] < value) {
return binarySearch(kind, {
array,
value,
start: mid+1,
end: end,
})
} else {
return binarySearch(kind, {
array,
value,
start: start,
end: mid-1,
})
}
}
- pode-se usar um min-heap de capacidade 2;
- ou two pointers
code
/**
* @param {number[]} numbers
* @returns {number|undefined}
*/
function findSecondLargest(numbers) { // O(n) em tempo e O(1) em espaço
if (numbers.length < 2) return numbers[0]
let max = Number.MIN_VALUE
let secondMax = Number.MIN_VALUE
for (const currNum of numbers) {
const newMax = Math.max(currNum, max)
const newSecondMax = Math.max(max, secondMax)
max = newMax
secondMax = newSecondMax
/*
if (currNum > max) {
secondMax = max
max = currNum
} else if (currNum > secondMax) {
if (max !== currNum)
secondMax = currNum
}
*/
}
return secondMax
}
findSecondLargest([-1, 10, 8, 9, 10, 9, -8, 11]) === 10