Передовой расширенный алгоритм: не говорите, что не понимаете проблему topk

внешний интерфейс алгоритм

введение

Сегодняшняя статья объясняет тему, которая активно используется в интервью с различными крупными компаниями (Tencent, Byte, Ali и т. д.): вопрос Top K, который будет представлен в следующем контексте:

  • В чем проблема Top K
  • Пять классических решений проблемы Top K
  • Быстрый обзор и резюме
  • Упражнение Top K Three Musketeers: минимум K чисел, K топовых высокочастотных элементов, K-й наименьший элемент (включая решения)

Давайте начнем ниже.

1. В чем проблема Top K

В чем проблема Top K? Проще говоря, это поиск первых K чисел с наибольшей частотой в наборе данных или первых K больших (конечно, лучших K маленьких) чисел.

Классические задачи Top K: наибольшее (наименьшее) число K, первые K высокочастотных элементов, K-й наибольший (наименьший) элемент.

Ниже приведен пример поиска K-го по величине элемента в массиве, чтобы представить решение проблемы Top K.

тема:

найти первое в несортированном массивеkсамый большой элемент. Обратите внимание, что вам нужно найти k-й самый большой элемент отсортированного массива.

Пример:

输入: [4,5,1,6,2,7,3,8] 和 k = 4
输出: 5

Во-вторых, решение: глобальная сортировка, взять k-е число

Самое простое, что мы можем придумать, это отсортировать массив (это может быть простейшая быстрая сортировка), просто взять первые K чисел, так просто

Код:

let findKthLargest = function(nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k-1]
};

Анализ сложности:

  • Временная сложность: O(nlogn)
  • Сложность пространства: O(logn)

Уведомление:

До версии движка V8 7.0, когда длина массива меньше 10,Array.prototype.sort()Используется сортировка вставками, в противном случае используется быстрая сортировка.

От быстрой сортировки отказались после версии движка V8 7.0, потому что это нестабильный алгоритм сортировки, и в худшем случае временная сложность упадет до O(n2).

Вместо этого используется гибридный алгоритм сортировки:TimSort.

Этот функциональный алгоритм изначально использовался в языке Python, строго говоря, он не принадлежит ни к одному из 10 вышеперечисленных алгоритмов сортировки, а относится к гибридному алгоритму сортировки:

Использование в подмассивах с небольшим объемом данныхСортировка вставками, затем используйтеСортировка слияниемСортировка слиянием отсортированных подмассивов, временная сложностьO(nlogn).

В-третьих, решение: локальная сортировка, барботирование

Теме нужно только спросить k-й самый большой элемент в массиве, нет необходимости сортировать массив.

Вы можете использовать Bubble Source, чтобы пузырировать наибольшее количество на данный момент каждый раз и только пузырьк K раз.

Анимированная демонстрация

Код

let findKthLargest = function(nums, k) {
    // 进行k轮冒泡排序
    bubbleSort(nums, k)
    return nums[nums.length-k]
}

let bubbleSort = function(arr, k) {
    for (let i = 0; i < k; i++) {
        // 提前退出冒泡循环的标识位
        let flag = false;
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                // 表示发生了数据交换
            }
        }
        // 没有数据交换
        if(!flag) break
    }
}

Анализ сложности:

  • Временная сложность: лучшая временная сложность O (n), средняя временная сложность O (n * k)
  • Космическая сложность: O(1)

В-четвертых, решение: до строительстваkМаленькая верхняя куча с самым большим элементом, возьмите вершину кучи

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

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

Конкретные шаги заключаются в следующем:

  • выйти вперед из массиваkколичество (0прибытьk-1биты), построить небольшую верхнюю кучу
  • отkБит начинает обход массива, и каждые данные сравниваются с верхним элементом маленькой верхней кучи, если он меньше верхнего элемента кучи, ничего не делать и продолжать обход следующего элемента, если он больше верхний элемент кучи, замените этот элемент.Соберите верхний элемент в кучу, а затем сложите его в маленькую верхнюю кучу.
  • После завершения обхода данные в верхней части кучи являются K-ми по величине данными.

Код:

let findKthLargest = function(nums, k) {
    // 从 nums 中取出前 k 个数，构建一个小顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(nums[i++]) 
    }
    buildHeap(heap, k)
    
    // 从 k 位开始遍历数组
    for(let i = k; i < nums.length; i++) {
        if(heap[1] < nums[i]) {
            // 替换并堆化
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    
    // 返回堆顶元素
    return heap[1]
};

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}

// 堆化
let heapify = (arr, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

Анализ сложности:

  • Временная сложность: для обхода массива требуется временная сложность O (n), а для одной кучи требуется временная сложность O (logk), поэтому временная сложность использования кучи для поиска задачи Top k составляет O (nlogk).
  • Пространственная сложность: O(k)

Воспользуйтесь преимуществами heap top k задач

Такого рода проблему Top k можно решить с помощью сортировки, но что, если нам нужно найти элементы Top k в динамическом массиве?

Динамические массивы могут вставлять или удалять элементы, нужно ли нам переупорядочивать массив каждый раз, когда мы решаем задачу Top k? Временная сложность каждого времени составляет O (nlogn)

Здесь вы можете использовать кучу, мы можем поддерживать небольшой размер верхней части кучи A k, когда данные добавляются в массив, его будет сравниваться с верхней частью элемента кучи, если элемент больше, чем верхний кучи, он заменит элемент куча верхнего элемента, а затем в верхнюю часть кучи кучи; если элемент меньше верхней части кучи, то без обработки. Таким образом, каждый раз, когда ищут верхнюю сложность задачи K (LOGK)

Можно просмотреть больше содержимого кучиAdvanced Front-End Algorithm 9: после прочтения этой статьи я больше не буду бояться сортировки в куче, Top K и опросов по медианным вопросам

5. Решение: оптимизация, алгоритм быстрого выбора

Будь то алгоритм сортировки или построение кучи для решения задачи Top k, мы прошли некоторое количество ненужных операций:

  • Если мы используем алгоритм сортировки, нам нужно только k-е наибольшее значение, но мы сортируем массив глобально или локально.
  • Если вы используете сортировку кучей, вам необходимо поддерживать размерkКуча (куча большая точка, верхняя часть маленькой кучи), в то время как тратить время очень дорого и сложность времениO(nlogk)

Итак, существует ли алгоритм для получения K-го по величине элемента без сортировки и без траты лишнего места?

Это про алгоритм быстрого выбора 😊

Алгоритм quickselect по идее похож на quicksort.Давайте популяризируем quicksort.Кто уже знает,может пропустить этот абзац.

Быстрый ряд

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

Процесс быстрой сортировки состоит всего из трех шагов:

  • Сначала выберите номер из последовательности в качестве ссылочного номера
  • Поместите все числа, большие этого числа, справа от него, а все числа, меньшие или равные ему, поместите слева от него (быстрая сортировка).partition)
  • Затем повторите описанные выше операции для левой и правой сторон эталона соответственно, пока массив не будет полностью отсортирован.

Конкретные шаги заключаются в следующем:

  • 1. Создайте два указателя на крайний левый и крайний правый концы массива соответственно.
  • 2, произвольно взять элемент в массиве в качестве эталона
  • 3. Левый указатель начинает двигаться вправо и натыкается на упор больше основания
  • 4. Правый указатель начинает двигаться влево, останавливается, когда встречает элемент, меньший, чем ссылка, и меняет местами элементы, на которые указывают левый и правый указатели.
  • 5. Повторяйте 3 и 4, пока левый указатель не превысит правый указатель.В это время значение, меньшее, чем эталонное значение, будет помещено в левую часть эталона, а значение, большее, чем эталонное значение, появится в правой части эталон
  • 6, а затем повторять описанные выше операции для левой и правой частей эталона до тех пор, пока массив не будет полностью отсортирован.

Заметили, как бенчмарки здесь выбраны Нангом? Самый простой способ сделать это — каждый раз выбирать крайний левый элемент в качестве ссылки:

Но это не лучший выбор для почти уже упорядоченных последовательностей, он приведет к худшей производительности алгоритма. Другой способ - выбрать средний номер или пройтиMath.random()Чтобы случайным образом выбрать число в качестве эталона, следующая реализация кода основана на случайном числе в качестве эталона.

Код

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

// 测试
let arr = [1, 3, 2, 5, 4]
quickSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]
// 第 2 个最大值
console.log(arr[arr.length - 2])  // 4

Быстрый ряд — это сортировка от мелкого к крупному, поэтомуkМаксимальное значение находится наn-kместо нахождения

Анализ сложности

  • Временная сложность: O(nlogn)
  • Пространственная сложность: O(nlogn)

алгоритм быстрого выбора

Выше мы реализовали быструю сортировку, чтобы получить k-е наибольшее значение, но это не обязательно так хлопотно.

Нам нужно только сравнить, находится ли позиция эталонного значения вn-kпозиция,

  • если меньше чемn-k, то k-е максимальное значение находится справа от эталонного значения, нам нужно только рекурсивно быстро отсортировать подпоследовательность справа от эталонного значения;
  • если больше, чемn-k, то k-е максимальное значение находится на стороне эталонного значения, нам нужно только рекурсивно быстро отсортировать подпоследовательность слева от эталонного значения;
  • если равноn-k, то k-е наибольшее значение является эталонным значением

Код:

let findKthLargest = function(nums, k) {
    return quickSelect(nums, nums.length - k)
};

let quickSelect = (arr, k) => {
  return quick(arr, 0 , arr.length - 1, k)
}

let quick = (arr, left, right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return arr[index]
    } else if(k < index) {
        // Top k 在左边
        return quick(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return quick(arr, index+1, right, k)
    }
  }
  return arr[left]
}

let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时，即都为datum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

Анализ сложности:

  • Временная сложность: средняя временная сложность составляет O (n), а временная сложность в худшем случае — O (n).2)
  • Космическая сложность: O(1)

Шестое, решение: продолжить оптимизацию алгоритма медианы медианы (BFPRT)

Также известен какМедианный алгоритм для медианы, его наихудшая временная сложность равна O(n) , которая определяется выражениемБлюм, Флойд, Пратт, Ривест, Тарьянпредложить. Идея алгоритма состоит в том, чтобы модифицировать метод выбора поворота алгоритма быстрого выбора, чтобы улучшить временную сложность алгоритма в худшем случае.

В алгоритме BFPTR изменен только алгоритм быстрого выбораPartionПри выборе эталонного значения в алгоритме quickselect мы можем выбрать первый элемент или последний элемент в качестве эталонного элемента, а оптимизированный может выбрать в качестве эталонного элемента случайный элемент, тогда как в алгоритме BFPTR каждый время Выберите медиану квинтилей в качестве базовой единицы (также известную как опорнаяpivot), цель этого состоит в том, чтобы сделать разделение более разумным, чтобы избежать наихудшего случая.

Шаги алгоритма BFPRT следующие:

  • Выберите сводную точку
    • Разделите n элементов по порядку наn/5группы по 5 элементов в каждой, отбросить все оставшиеся
    • за этоn/5Каждый набор групп, использующих сортировку вставками, найден в соответствующей медиане
    • Для всех медиан, найденных на предыдущем шаге, вызовите алгоритм BFPRT, чтобы найти их медианы в качестве точки опоры;
  • За точку разделения возьмем стержень, поставим меньший, чем стержень, слева, а больший, чем стержень, справа;
  • Определите положение опорной точки и размер k и выборочно рекурсивно влево или вправо

Код:

let findKthLargest = function(nums, k) {
    return nums[bfprt(nums, 0, nums.length - 1, nums.length - k)]
}

let bfprt = (arr, left , right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return index
    } else if(k < index) {
        // Top k 在左边
        return bfprt(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return bfprt(arr, index+1, right, k)
    }
  }
  return left
}

let partition = (arr, left, right) => {
  // 基准
  var datum = arr[findMid(arr, left, right)],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时，即都为datum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}

/**
 * 数组 arr[left, right] 每五个元素作为一组，并计算每组的中位数，
 * 最后返回这些中位数的中位数下标（即主元下标）。
 *
 * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思，
 * 这样可以始终保持 k 大于 0。
 */
let findMid = (arr, left, right) => {
    if (right - left < 5)
        return insertSort(arr, left, right);

    let n = left - 1;

    // 每五个作为一组，求出中位数，并把这些中位数全部依次移动到数组左边
    for (let i = left; i + 4 <= right; i += 5)
    {
        let index = insertSort(arr, i, i + 4);
        swap(arr[++n], arr[index]);
    }

    // 利用 bfprt 得到这些中位数的中位数下标（即主元下标）
    return findMid(arr, left, n);
}

/**
 * 对数组 arr[left, right] 进行插入排序，并返回 [left, right]
 * 的中位数。
 */
let insertSort = (arr, left, right) => {
    let temp, j
    for (let i = left + 1; i <= right; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= left && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return ((right - left) >> 1) + left;
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

Анализ сложности:

Почему 5?

Почему в алгоритме BFPRT выбрано 5 групп?

Во-первых, исключаются четные числа, потому что для нечетных чисел легче вычислить медиану.

Если выбрано 3,

, количество элементов операнда по-прежнемуn.

Если вы выберете 7, 9 или больше, время, затрачиваемое на сортировку вставками, постоянно увеличивается.cОн будет огромным, и это небольшая потеря.

7. Обзор и заключение

Напоследок резюмируем, что найти задачу topk несложно, есть в основном следующие идеи:

  • Общая сортировка: O(nlogn)
  • частичный заказ: только верхние k самых больших значений в пузырьковой сортировке, O(n*k)
  • использовать кучу: O(nlogk)
  • подсчет или сортировка ведра: сортировка подсчетом используется для k самых высоких значений, а временная сложность составляет O(n + m), где m представляет диапазон данных; сортировка сегментов используется для наибольшей частоты k, а временная сложность составляет O(n). ;Но оба требуют, чтобы входные данные были целыми числами с определенным диапазоном, эта статья не представляет слишком многого, вы можете перейти кGitHub.com/sister/JA…См. серию кучи для получения дополнительной информации.
  • Оптимизация: алгоритм быстрого выбора: Средний O (n), худший o (n2)
  • Продолжить оптимизацию: алгоритм средних чисел (BFPRT): наихудший O (n)

Вот краткое описание последних двух вариантов:

  • Прежде всего, вам нужно знать, что такое быстрая сортировка.Процесс быстрой сортировки состоит из трех шагов: во-первых, выберите число из последовательности в качестве ссылочного номера, поместите все числа слева от него (быстрая сортировкаpartition); затем повторите вышеуказанные операции для левой и правой сторон эталона, пока массив не будет полностью отсортирован

  • Алгоритм быстрого выбора: быстрая сортировка сортирует все данные, и нам нужно только k-е наибольшее значение, поэтомуquickselectОптимизировать быструю сортировку: после каждого выполнения быстрой сортировки (partition), сравните, находится ли позиция опорного значения вn-k(к-е наибольшее = n-к-е наименьшее, n - длина массива) позиция, если меньшеn-k, то k-е максимальное значение находится справа от эталонного значения, нам просто нужно рекурсивно отсортировать подпоследовательность справа от эталонного значения; если оно большеn-k, то k-е максимальное значение находится на стороне эталонного значения, нам нужно только рекурсивно отсортировать подпоследовательность слева от эталонного значения, если она равнаn-k, то k-е максимальное значение является эталонным значением, средняя временная сложность равна O(n), а временная сложность в наихудшем случае равна O(n2), в худшем случае временная сложность все еще очень высока

  • Алгоритм медианы медиан (bfprt): Идея этого алгоритма состоит в том, чтобы изменить быстрый выбор (quickselect) метод выбора поворота алгоритма для улучшения временной сложности алгоритма в худшем случае

Наконец, прикрепите классические практические вопросы из Top K вопросов, слишком много вопросов для решения, перейдите в репозиторий git, чтобы просмотреть ответы.

Прекрасное прошлое

Спасибо за прочтение

Добро пожаловать, чтобы обратить внимание на «Front-end Bottle Master», ответьте на «Exchange», чтобы присоединиться к группе внешнего обмена!

Добро пожаловать, чтобы обратить внимание на «Front-end Bottle Master», ответьте «Алгоритм», чтобы автоматически присоединиться и построить полную структуру данных и систему алгоритмов от 0 до 1!

Здесь мистер Боттл не только представляет алгоритм, но и объединяет алгоритм с различными полями интерфейса, включая браузеры, HTTP, V8, React, исходный код Vue и т. д.

Здесь (группа алгоритмов) вы можете изучать большой вопрос по программированию заводского алгоритма (Ali, Tencent, Baidu, Byte и т. д.) или литкод каждый день, а мистер Бутылка ответит на него на следующий день!

Кроме того, каждую неделю есть рукописные вопросы по исходному коду, и мистер Боттл тоже на них ответит!

Категории