Сравнение типов данных набора в [закрытом] C#
Мой код ниже является алгоритмом O (k). Он не работает на определенном граничном случае (вероятно, по одному в каждом направлении: x и y). Я перечислил крайний случай, чтобы кто-то мог это исправить. Я не собираюсь это исправлять, потому что мне пора спать.
Краткое описание алгоритма: вам нужно только отслеживать два кандидата #, которые могут быть наименьшими, один при движении в направлении x и один при движении в направлении y. Подумайте об этом, и это может иметь для вас смысл.
enum Direction {
X,
Y
};
struct Index
{
Index(int unsigned x, int unsigned y)
: x(x),
y(y)
{}
void operator = (Index const & rhs)
{
x = rhs.x;
y = rhs.y;
}
int unsigned x;
int unsigned y;
};
int unsigned solve(int unsigned i_k, int unsigned ** i_data, int unsigned i_n)
{
if (1 == i_k) {
return i_data[0][0];
}
Direction dir = X;
Index smaller(0,0);
Index larger(0,0);
if (i_data[1][0] < i_data[0][1]) {
dir = X;
smaller = Index(1,0);
larger = Index(0,1); }
else {
dir = Y;
smaller = Index(0,1);
larger = Index(1,0);
}
for (int unsigned i = 0; i < (i_k - 2); ++i) {
int unsigned const x = smaller.x;
int unsigned const y = smaller.y;
if (X == dir) {
if ((x + 1) == i_n) {
// End of row
smaller = larger;
larger.x += 1;
dir = Y; }
else if (i_data[x + 1][y] < i_data[larger.x][larger.y]) {
smaller.x += 1; }
else {
smaller = larger;
larger = Index(x + 1, y);
dir = Y;
} }
else {
if ((y + 1) == i_n) {
// End of col
smaller = larger;
larger.y += 1;
dir = X; }
else if (i_data[x][y + 1] < i_data[larger.x][larger.y]) {
smaller.y += 1; }
else {
smaller = larger;
larger = Index(x, y + 1);
dir = X;
}
}
}
return i_data[smaller.x][smaller.y];
}
не работает в следующем краевом случае (где мы достигли конца строки). Я иду спать, не стесняйтесь исправить это дело:
size = 4;
data = createMatrix(size);
data[0][0] = 1; data[1][0] = 6; data[2][0] = 10; data[3][0] = 11;
data[0][1] = 3; data[1][1] = 7; data[2][1] = 12; data[3][1] = 14;
data[0][2] = 4; data[1][2] = 8; data[2][2] = 13; data[3][2] = 15;
data[0][3] = 5; data[1][3] = 9; data[2][3] = 19; data[3][3] = 20;
answer = solve(14, data, size);
assertAnswer(answer, 15, ++testNum);
deleteMatrix(data, size);
2 ответа
Следующий контент был первоначально взят из MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc (но с тех пор ссылка умерла).
Как и на изображении выше, содержимое изначально было представлено в виде таблицы (которую StackOverflow не поддерживает).
Учитывая, что изображение нелегко проиндексировать, ниже приведено несколько грубое программное преобразование информации в списки:
Массив
- добавить в конец:
O (n) - удалить из конца:
O (n) - вставить посередине:
O (n) - удалить из середины:
O (n) - Произвольный доступ:
O (1) - Доступ по порядку:
O (1) - Поиск определенного элемента:
O (n) - Примечания: Наиболее эффективное использование памяти; использовать в случаях, когда размер данных фиксирован.
Список
- добавить в конец:
лучший случай O (1); наихудший случай O (n) - удалить с конца:
O (1) - вставить в середину:
O (n) - удалить из середины:
O (n) - Произвольный доступ:
O (1) - Доступ по порядку:
O (1) - Поиск определенного элемента:
O (n) - Примечания: Реализация оптимизирован по скорости. Во многих случаях List будет лучшим выбором.
Сборник
- добавить в конец:
лучший случай O (1); наихудший случай O (n) - удалить с конца:
O (1) - вставить в середину:
O (n) - удалить из середины:
O (n) - Произвольный доступ:
O (1) - Доступ по порядку:
O (1) - Поиск определенного элемента:
O (n) - Примечания: Список - лучший выбор, если только он не будет опубликован как API.
LinkedList
- добавить в конец:
O (1) - удалить с конца:
O (1) - вставить в середину:
O (1) - удалить от середины:
O (1) - Произвольный доступ:
O (n) - Доступ по порядку:
O (1) - Поиск определенного элемента:
O (n) - Примечания: Многие операции выполняются быстро, но следите за согласованностью кеша.
Стек
- добавить в конец:
лучший случай O (1); наихудший случай O (n) - удалить с конца:
O (1) - вставить в середину:
N / A - удалить из середины:
N / A - Случайно Доступ:
Н / Д - Доступ по порядку:
Н / Д - Поиск определенного элемента:
Н / Д - Примечания: Не следует выбирать для причины производительности, но алгоритмические.
Очередь
- добавить в конец:
лучший случай O (1); наихудший случай O (n) - удалить с конца:
O (1) - вставить в середину:
N / A - удалить из середины:
N / A - Случайно Доступ:
Н / Д - Доступ по порядку:
Н / Д - Поиск определенного элемента:
Н / Д - Примечания: Не следует выбирать для причины производительности, но алгоритмические.
Словарь
- добавить в конец:
лучший случай O (1); наихудший случай O (n) - удалить с конца:
O (1) - вставить посередине:
лучший случай O (1); наихудший случай O (n) - удалить из середины:
O (1) - Произвольный доступ:
O (1) * - Доступ по порядку:
O (1) * - Поиск определенного элемента:
O (1) - Примечания: Хотя время доступа по порядку является постоянным, оно обычно медленнее, чем другие структуры, из-за чрезмерных затрат времени на поиск ключ.
Это не шпаргалка, но хорошее место для начала изучения: Классы коллекций (Руководство по программированию C #) .
Изменить: I будет специально рассматривать этот связанный раздел: Выбор класса коллекции .
Обязательно выберите свой System.Collections внимательно. Использование неправильного типа может ограничить ваши использование коллекции.