Поиск элемента в массиве, который не повторяется кратным три раза?

Ответ 1

Это можно сделать в O (n) времени и O (1) пространстве.

Вот как вы можете это сделать с постоянным пространством в С#. Я использую идею "xor, за исключением бит из трех состояний". Для каждого установленного бита операция "xor" увеличивает соответствующее значение 3-состояния.

Конечным результатом будет номер, двоичное представление которого имеет 1s в местах, которые имеют 1 или 2 в конечном значении.

void Main() {
    Console.WriteLine (FindNonTriple(new uint[] 
                        {1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3} ));
    // 1

    Console.WriteLine (FindNonTriple(new uint[] 
                        {3, 2, 1, 3, 2, 1, 3, 2, 1, 4, 4, 4, 4} ));
    // 4
}

uint FindNonTriple(uint[] args) {
    byte[] occurred = new byte[32];

    foreach (uint val in args) {
        for (int i = 0; i < 32; i++) {
            occurred[i] = (byte)((occurred[i] + (val >> i & 1)) % 3);
        }
    }

    uint result = 0;
    for (int i = 0; i < 32; i++) {
        if (occurred[i] != 0) result |= 1u << i;
    }
    return result;
}

Ответ 2

Очевидное решение сделать это в постоянном пространстве - это сортировать его с помощью алгоритма на месте, а затем сканировать один раз над массивом.

К сожалению, для этого обычно требуется время O (n log n) и O (1).

Но поскольку записи имеют ограниченную длину ключа (32 бит), вы можете использовать в качестве сортировки сортировки алгоритмов сортировки (существуют на месте сортировка по методу radix, они нестабильны, но это не имеет значения здесь). Там у вас время O (n) и O (1).

РЕДАКТИРОВАТЬ. Кстати, вы могли бы использовать этот подход, чтобы найти также ВСЕ числа, которые отображаются не кратно 3 раза, в случае, если вы позволите, чтобы более одного номера могли иметь это свойство.

Ответ 3

Вы ищете элемент с номером rep, который отличен от нуля (mod 3). Я думаю, что я бы сделал это рекурсивно:

• разделить массив пополам
• найдите элементы с числом rep, которое не равно нулю (mod 3) в каждой половине
• объединить половинки, сохранить подсчеты для неравных ключей и добавить подсчеты для равных ключей
• вычеркивать любой с count = 0 (mod 3)
• возвращает это как набор значений для текущей части ввода.

Даже не пытаясь оптимизировать вещи за основным алгоритмом (например, не беспокоясь о сохранении только двух бит на счетчик), это, похоже, очень хорошо. Я включил код для создания достаточно большого тестового примера (например, 1500+ элементов) и распечатал размеры создаваемых карт. В любой момент времени на картах создается максимум около 50 элементов (т.е. Он использует только две карты за раз, а наибольшая из них - около 25 элементов). Технически, поскольку это означает, я считаю, что в настоящее время это что-то вроде O (N log N), но если вы переключились на контейнер, основанный на хеше, я считаю, что вы ожидаете O (N).

#include <map>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <time.h>

class zero_mod { 
    unsigned base;
public:
    zero_mod(unsigned b) : base(b) {}

    bool operator()(std::pair<int, int> const &v) { 
        return v.second % base == 0; 
    }
};

// merge two maps together -- all keys from both maps, and the sums 
// of equal values.
// Then remove any items with a value congruent to 0 (mod 3)
//
std::map<int, int> 
merge(std::map<int, int> const &left, std::map<int, int> const &right) { 
    std::map<int, int>::const_iterator p, pos;
    std::map<int, int> temp, ret;

    std::copy(left.begin(), left.end(), std::inserter(temp, temp.end()));
    for (p=right.begin(); p!=right.end(); ++p) 
        temp[p->first] += p->second;
    std::remove_copy_if(temp.begin(), temp.end(), 
                        std::inserter(ret, ret.end()), 
                        zero_mod(3));
    return ret;
}   

// Recursively find items with counts != 0 (mod 3):    
std::map<int, int> 
do_count(std::vector<int> const &input, size_t left, size_t right) { 
    std::map<int, int> left_counts, right_counts, temp, ret;

    if (right - left <= 2) {
        for (size_t i=left; i!=right; ++i) 
            ++ret[input[i]];
        return ret;
    }
    size_t middle = left + (right-left)/2;
    left_counts = do_count(input, left, middle);
    right_counts = do_count(input, middle, right);
    ret = merge(left_counts, right_counts);

    // show the size of the map to get an idea of how much storage we're using.
    std::cerr << "Size: " << ret.size() << "\t";
    return ret;
}

std::map<int, int> count(std::vector<int> const &input) { 
    return do_count(input, 0, input.size());
}

namespace std { 
    ostream &operator<<(ostream &os, pair<int, int> const &p) { 
        return os << p.first;
    }
}

int main() {
    srand(time(NULL));
    std::vector<int> test;

    // generate a bunch of data by inserting packets of 3 items    
    for (int i=0; i<100; i++) {
        int packets = std::rand() % 10;
        int value = rand() % 50;
        for (int i=0; i<packets * 3; i++) 
            test.push_back(value);
    }

    // then remove one item, so that value will not occur a multiple of 3 times
    size_t pos = rand() % test.size();
    std::cerr << "Removing: " << test[pos] << " at position: " << pos << "\n";

    test.erase(test.begin()+pos);

    std::cerr << "Overall size: " << test.size() << "\n";

    std::random_shuffle(test.begin(), test.end());

    // Note that we use a map of results, so this will work if multiple values
    // occur the wrong number of times.    
    std::map<int, int> results = count(test);

    // show the results. Should match the value shown as removed above:
    std::copy(results.begin(), results.end(), 
        std::ostream_iterator<std::pair<int, int> >(std::cout, "\n"));
    return 0;
}