Как перезагрузить centos в докере?

Существует и не требует, чтобы элементы имели порядок.

Чтобы быть формальным, мы имеем дело с мультимножествами (также называемыми мешками .) В следующем случае для мультимножества S :

• v ( e , S ) - кратность элемента e в S , т. е. количество раз, когда оно происходит (кратность равна нулю, если e вообще не является членом S .)
• #S - мощность S , т. е. количество элементов в S , считающих кратность.
• ⊕ - мультимножественная сумма: если S = L ⊕ R , тогда S содержит все элементы из L и R , подсчитывающие кратность, т.е. v ( e ; S ) = v ( e ; L ) + v ( e ; R ) для любого элемента e . (Это также показывает, что кратность может быть вычислена «делением и покорением».)
• [ x ] - наибольшее целое число, меньшее или равное x .

Элемент m большинства S , если он существует, является тем элементом, что 2 v ( m ; S )> #S .

Назовем L и R a расщепление S , если L ​​ ⊕ R = S и четное расщепление , если | #L - #R | ≤ 1. То есть, если n = #S четно, L и R имеют ровно половину элементов из S , и если n нечетно, чем один имеет мощность [ n / 2], а другой имеет мощность [ n /2]+1.

Для произвольного раскола S на L и R два наблюдения :

1. Если ни L , ни R не имеют элемента большинства, то S не может: для любого элемента e , 2 v ( e ; S ) = 2 v ( e ; L ) + 2 v ( e ; R ) ≤ #L + #R = #S .
2. Если один из L и R имеет мажоритарный элемент m с кратностью k , то он является мажоритарным элементом S , только если он имеет кратность r в другой половине, с 2 ( k + r )> #S .

Алгоритм majo rity ( S ) ниже возвращает либо пару ( m , k ), указывая, что m является элементом большинства с k вхождения или none :

1. Если S пуст, верните none ; если S имеет только один элемент m , затем верните ( m , 1). В противном случае:
2. Сделайте ровное расщепление S на две половины L и R .
3. Пусть ( m , k ) = большинство ( L ), если не none : a. Пусть k ' = k + v ( m ; R ). б. Возврат ( m , k '), если 2 k' > n .
4. В противном случае let ( m , k ) = большинство ( R ), если не none : a. Пусть k ' = k + v ( m ; L ). б. Возврат ( m , k '), если 2 k' > n .
5. В противном случае return none .

Обратите внимание, что алгоритм по-прежнему корректен, даже если split не является четным. Разделение равномерно, хотя, скорее всего, будет лучше работать на практике.

Добавление

Сделал вывод в терминале явным в описании алгоритма выше. Пример кода C ++:

struct majority_t {
    int m; // majority element
    size_t k; // multiplicity of m; zero => no majority element

    constexpr majority_t(): m(0), k(0) {}
    constexpr majority_t(int m_,size_t k_): m(m_), k(k_) {}

    explicit operator bool() const { return k>0; }
};

static constexpr majority_t no_majority;

size_t multiplicity(int x,const int *arr,size_t n) {
    if (n==0) return 0;
    else if (n==1) return arr[0]==x?1:0;

    size_t r=n/2;
    return multiplicity(x,arr,r)+multiplicity(x,arr+r,n-r);
}

majority_t majority(const int *arr,size_t n) {
    if (n==0) return no_majority;
    else if (n==1) return majority_t(arr[0],1);

    size_t r=n/2;
    majority_t left=majority(arr,r);
    if (left) {
        left.k+=multiplicity(left.m,arr+r,n-r);
        if (left.k>r) return left;
    }

    majority_t right=majority(arr+r,n-r);
    if (right) {
        right.k+=multiplicity(right.m,arr,r);
        if (right.k>r) return right;
    }

    return no_majority;
}