Мое решение (O(N)
) не использует дополнительную память, но массив должен быть отсортирован (мой класс использует алгоритм сортировки вставки, но это не имеет значения.):
public class MyArray
{
//data arr
private int[] _arr;
//field length of my arr
private int _leght;
//counter of duplicate
private int countOfDup = 0;
//property length of my arr
public int Length
{
get
{
return _leght;
}
}
//constructor
public MyArray(int n)
{
_arr = new int[n];
_leght = 0;
}
// put element into array
public void Insert(int value)
{
_arr[_leght] = value;
_leght++;
}
//Display array
public void Display()
{
for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " ");
}
//Insertion sort for sorting array
public void InsertSort()
{
int t, j;
for (int i = 1; i < _leght; i++)
{
t = _arr[i];
for (j = i; j > 0; )
{
if (_arr[j - 1] >= t)
{
_arr[j] = _arr[j - 1];
j--;
}
else break;
}
_arr[j] = t;
}
}
private void _markDuplicate()
{
//mark duplicate Int32.MinValue
for (int i = 0; i < _leght - 1; i++)
{
if (_arr[i] == _arr[i + 1])
{
countOfDup++;
_arr[i] = Int32.MinValue;
}
}
}
//remove duplicates O(N) ~ O(2N) ~ O(N + N)
public void RemoveDups()
{
_markDuplicate();
if (countOfDup == 0) return; //no duplicate
int temp = 0;
for (int i = 0; i < _leght; i++)
{
// if duplicate remember and continue
if (_arr[i] == Int32.MinValue) continue;
else //else need move
{
if (temp != i) _arr[temp] = _arr[i];
temp++;
}
}
_leght -= countOfDup;
}
}
и Main
static void Main(string[] args)
{
Random r = new Random(DateTime.Now.Millisecond);
int i = 11;
MyArray a = new MyArray(i);
for (int j = 0; j < i; j++)
{
a.Insert(r.Next(i - 1));
}
a.Display();
Console.Out.WriteLine();
a.InsertSort();
a.Display();
Console.Out.WriteLine();
a.RemoveDups();
a.Display();
Console.ReadKey();
}
Цитата из статьи Википедии о веб-хранилище :
Веб-хранилище можно упрощенно рассматривать как усовершенствование файлов cookie, обеспечивая гораздо большую емкость хранилища ( 10 МБ на источник в Google Chrome ( https://plus.google.com/u/0/+FrancoisBeaufort/posts/S5Q9HqDB8bh ), Mozilla Firefox и Opera; 10 МБ на область хранения в Internet Explorer ) и улучшенные программные интерфейсы .
А также цитата из статьи Джона Ресига [опубликовано в январе 2007 г.]:
Место для хранения
Подразумевается, что с хранилищем DOM, у вас значительно больше места для хранения пространство, чем типичный пользовательский агент ограничения, накладываемые на файлы cookie. Однако предоставленная сумма не определено в спецификации, и не транслируется осмысленно пользовательский агент.
Если вы посмотрите исходный код Mozilla мы видим, что по умолчанию используется 5120 КБ размер хранилища для всего домена. Это дает вам значительно больше места работать с типичным 2 КБ куки.
Однако размер этого хранилища могут быть настроены пользователем (так что 5 МБ дискового пространства не гарантируется, и это не подразумевается), а пользовательский агент (Opera, например, может предоставлять только 3 МБ - но только время покажет.)
На самом деле Opera не имеет ограничения в 5 МБ. Он предлагает увеличить лимит, поскольку приложениям требуется больше. Пользователь может даже выбрать «Неограниченное хранилище» для домена.
Вы можете легко проверить пределы / квоту localStorage самостоятельно.