ТГиК-2019-Семинар-09.12.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

siftDown

SiftDown - процедура, которая пересобирает кучу сверху вниз так, чтобы она удовлетворяла условию (1). В других источниках функция может называться Heapify или Heapify_down

Если i-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами i-й элемент с наименьшим из его сыновей, после чего выполняем siftDown для этого сына. Процедура выполняется за время O(log(n)).

Разбор задач к 15 неделе

1.K-й по величине элемент массива

Условие:

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

Пример 1:

Входные данные: [3,2,1,5,6,4] и k = 2

Вывод: 5

Пример 2:

Входные данные: [3,2,3,1,2,4,5,5,6] и k = 4

Вывод: 4

Примечание:

Можно предположить, что k всегда допустимо, 1 ≤ k ≤ длина массива.

Решение:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        for (int i=nums.size()/2+1; i>0;--i){
            siftDown(i-1,nums);
}
    int ans=0;
        
        for (int i=0; i<k; i++){
            ans=extractMax(nums);
        }
        return ans;
    }
    
    void siftDown(size_t i, vector<int>& heap){
        while (2*i+1 < heap.size()){
            int left=2*i+1;
            int right=2*i+2;
            int m=2*i+1;
            if (right < heap.size() && heap[right]>heap[m]){
                m=right;
            }
            if (heap[i]>=heap[m]) break;
            swap(heap[i],heap[m]);
            i=m;
        }
    }
    
    int extractMax(vector<int>& heap){
        int max=heap[0];
        swap(heap[0],heap[heap.size()-1]);
        heap.erase(heap.begin()+heap.size()-1);
        siftDown(0,heap);
        return max;   
    }
};

2.Вес последнего камня

Условие:

У нас есть коллекция камней, каждый камень имеет положительный целочисленный вес.

Каждый ход мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y с x <= y. Результат этого удара:

Если x == y, оба камня полностью разрушены;

Если x! = Y, камень с весом x полностью разрушается, а камень с весом y имеет новый вес y-x.

В конце остается максимум 1 камень. Верните вес этого камня (или 0, если камней не осталось.)

Пример 1:

Входные данные: [2,7,4,1,8,1]

Выход: 1

Объяснение:

Мы объединяем 7 и 8, чтобы получить 1, так что массив преобразуется в [2,4,1,1,1], то,

мы объединяем 2 и 4, чтобы получить 2, так что массив преобразуется в [2,1,1,1], то,

мы объединяем 2 и 1, чтобы получить 1, так что массив преобразуется в [1,1,1], то,

мы объединяем 1 и 1, чтобы получить 0, так что массив преобразуется в [1], то это значение последнего камня.

Примечание:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

Решение:

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
         for (int i = stones.size() / 2 + 1; i >= 0; i--) {
            siftDown(i, stones);
        }

        while (stones.size() >= 2) {
            int y = extractMax(stones);
            int x = extractMax(stones);

            if (x != y) {
                insert(y - x, stones);
            }
        }

        return stones.empty() ? 0 : stones[0];
    }

    void siftDown(size_t i, vector<int> & heap) {
        while (2*i + 1 < heap.size()) {
            int left = 2*i + 1;
            int right = 2*i + 2;

            int m = left;
            if (right < heap.size() && heap[right] > heap[left])
                m = right;

            if (heap[i] >= heap[m])
                break;

            swap(heap[i], heap[m]);
            i = m;
        }
    }

    void siftUp(size_t i, vector<int> & heap) {
        int par = (i - 1) / 2;
        while (par >= 0 && heap[i] >= heap[par]) {
            swap(heap[i], heap[par]);
            i = par;
            par = (i - 1) / 2;
        }
    }

    int extractMax(vector<int> & heap) {
        int max = heap[0];

        swap(heap[heap.size() - 1], heap[0]);

        heap.erase(heap.begin() + heap.size() - 1);

        siftDown(0, heap);
        return max;
    }


    void insert(int val, vector<int> & heap) {
        heap.push_back(val);
        siftUp(heap.size() - 1, heap);
    }
};

3.Уродливый номер II

Условие:

Написать программу нахождения n-го уродливый номер. Уродливые числа-это положительные числа, простые множители которых включают только 2, 3, 5.

Пример:

Вход: n = 10

Выход: 12

Объяснение: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 это последовательность первых 10 уродливых чисел.

Примечание:

  • 1 обычно рассматривается как уродливое число.
  • n не превышает 1690.

Решение:

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<long long> nums={1};
        unordered_set<long long> s;
        s.insert(1);
        vector<long long> primes = {2,3,5};
        
        long long min;
        while (n>0){
            min=extractMin(nums);
            for (int a: primes){
                if (s.find(min*a)==s.end()){
                    Insert(min*a,nums);
                    s.insert(min*a);
                }
            }
            n--;
        }
        return min;
    }
    
     void Insert(long long val, vector<long long>& heap){
        heap.push_back(val);
        siftUp(heap.size()-1, heap);
    }
    
     int extractMin(vector<long long>& heap){
        int min=heap[0];
        swap(heap[0],heap[heap.size()-1]);
        heap.erase(heap.begin()+heap.size()-1);
        siftDown(0,heap);
        return min;
    }
    
     void siftDown(size_t i, vector<long long>& heap){
        while (2*i+1 < heap.size()){
            int left=2*i+1;
            int right=2*i+2;
            int m=2*i+1;
            if (right < heap.size() && heap[right]<heap[m]){
                m=right;
            }
            if (heap[i]<heap[m]) break;
            swap(heap[i],heap[m]);
            i=m;
        }
    }
    
    void siftUp (size_t i, vector<long long>& heap){
        int par=(i-1)/2;
        while (i>0 && heap[i]<heap[par]){
            swap(heap[i],heap[par]);
            i=par;
            par=(i-1)/2;
        }
    }
};

4.Топ К Частых Элементов

Условие:

Если задан непустой массив целых чисел, вернуть k наиболее часто встречающихся элементов.

Пример 1:

Входные данные: nums = [1,1,1,2,2,3], k = 2

Выход: [1,2]

Пример 2:

Входные данные: nums = [1], k = 1

Вывод: [1]

Примечание:

  • Можно предположить, что k всегда удовлетворяет условию, 1 ≤ k ≤ количество уникальных элементов.
  • Временная сложность вашего алгоритма должна быть лучше, чем O(n log n), где n-размер массива.

Решение:

class Solution {
public:
         struct Node{
            int val;
            int freq;
            Node(int val_, int freq_): val(val_), freq(freq_){}
        };
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        for (int a:nums) {
            m[a]+=1;
        }
        
        vector<Node> heap;
        for (auto it = m.begin(); it != m.end(); ++it){
            Insert(heap, Node(it->first, it->second));
        }
        vector<int> ans;
        for (int i=0; i<k; ++i){
            ans.push_back(extractMax(heap).val);
        }
        return ans;
        
        }
    
     void siftDown(size_t i, vector<Node>& heap){
        while (2*i+1 < heap.size()){
            int left=2*i+1;
            int right=2*i+2;
            int m=2*i+1;
            if (right < heap.size() && (heap[right]).freq > (heap[m]).freq){
                m=right;
            }
            if ((heap[i]).freq >= (heap[m]).freq) break;
            swap(heap[i],heap[m]);
            i=m;
        }
    }
    
    Node extractMax(vector<Node>& heap){
        Node max=heap[0];
        swap(heap[0],heap[heap.size()-1]);
        heap.erase(heap.begin()+heap.size()-1);
        siftDown(0,heap);
        return max;
    }
    
     void Insert(vector<Node>& heap, Node val){
        heap.push_back(val);
        siftUp(heap.size()-1, heap);
    }
    
     void siftUp (size_t i, vector<Node>& heap){
        int par=(i-1)/2;
        while (i>0 && (heap[i]).freq > (heap[par]).freq){
            swap(heap[i],heap[par]);
            i=par;
            par=(i-1)/2;
        }
    }
};