Найти число повторений числа в массиве меньше, чем O (n ^ 2) - PullRequest
Новая
       2

Найти число повторений числа в массиве меньше, чем O (n ^ 2)

3 голосов
/ 21 апреля 2011

Пример кода, который я написал. Но это n ^ 2 

int a[]={1,4,1,5,2,2,4,3,4,1};
int b[][]=new int[5][2];
int i,j,k=0,count=1;
boolean temp=false;
for(i=0;i<a.length;i++)
{
    for(j=0;j<5;j++)
    {
        if(a[i]==b[j][0])
        {   temp=true;
            b[j][1]++;
            break;
        }
    }

    if(temp==false)
    {
        b[k][0]=a[i];
        b[k][1]=1;
        k++;    
    }
    temp=false;
}
for(i=0;i<5;i++)
{
    for(j=0;j<1;j++)
    {
    System.out.println(b[i][j]+" is repeated "+b[i][j+1]+" times");
    }
}

Ответы [ 9 ]

7 голосов
/ 21 апреля 2011

Вот решение в псевдокоде: 

Map<Int, Int> histogram;
for(number in array) {
    histogram[number]++;
}

Теперь histogram[somenumber] содержит число раз, которое число находится в массиве - в O(n) при условии, что Map ищет элементы в O(1)

5 голосов
/ 21 апреля 2011

Вариант 1: жертвовать памятью ради скорости.

  • Используйте структуру данных, например HashMap, для записи частот каждого числа.
  • Выполните итерацию в течение O (n) времени, чтобы построить счетчики частоты, затем либо итерируйте весь HashMap, либо извлеките одно значение.

Вариант 2: сортировка

  • Сортировка, затем либо итерация по всей отсортированной структуре, либо O (log n) для поиска определенного значения.
    • Быстрая сортировка имеет среднее значение n log n, O (n ^ 2) наихудший случай, место для памяти.
    • Mergesort или heapsort имеют значение O (n log n), но занимают дополнительную память при сортировке
3 голосов
/ 21 апреля 2011

псевдокод: 

counts = dictionary default to 0

for each element in list:
    counts[element]+=1

О (п)

2 голосов
/ 21 апреля 2011

Вы должны использовать, например. сортировка слиянием для сортировки массива, а затем с помощью простого цикла for просматривают весь массив для подсчета повторов.

Сортировка слиянием имеет n * log (n), и цикл for для поиска повторов также быстр.

1 голос
/ 21 апреля 2011

Вы можете достичь за O (n) времени, создав другую структуру данных, например карту. Пример: int a [] = {1,4,1,5,2,2,4,3,4,1}; 

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for(int i = 0; i < a.length ; i++)
{
    if(map.containsKey(a[i]))
    {
        map.put(a[i], map.get(a[i])+1);
    }
    else
    {
        map.put(a[i], 1);
    }
}

System.out.print(map);

Результат: {1 = 3, 2 = 2, 3 = 1, 4 = 3, 5 = 1}

1 голос
/ 21 апреля 2011

Алгоритм быстрой сортировки должен быть намного быстрее, чем O (n ^ 2), и после него следует группа, которая является O (n), должна быть еще быстрее, чем O (n ^ 2).

Поэтому в псевдокоде: 

    group (sort [1,2,3,3,2,1])   =>   [(1,2), (2,2), (3,2)]
0 голосов
/ 21 апреля 2011

Сокращение O (n ^ 2) до O (n * log n) в этом случае просто:

  1. Сортировка чисел с использованием heapsort / quicksort ... O (n * log n)
  2. Пройдите по массиву один раз, посчитайте уникальные элементы и получите их счет ... O (n)

Сохранение сбалансированного по высоте дерева с числами в качестве ключей наряду с количеством вхождений - еще одинидея, которая даст O (n * log n).Я не вижу решения O (n) без использования хэш-таблицы, подобной структуре данных, которая доступна в большинстве языков.

0 голосов
/ 21 апреля 2011

Если вы можете изменить существующий массив, вы можете сделать это. Его O (n log (n)) и не создает новых объектов. (Если вы не можете изменить оригинал, вы можете клонировать его.) Это гораздо эффективнее, чем сохранение карты. ;) 

int a[] = {1, 4, 1, 5, 2, 2, 4, 3, 4, 1};

Arrays.sort(a);
int last = a[0];
int count = -1; 
for (int i : a) {
    if (i == last) {
        count++;
        continue;
    }
    System.out.println("Number " + last + " found " + count + " times.");
    count = 1;
    last = i;
}
System.out.println("Number " + last + " found " + count + " times.");

печать 

Number 1 found 3 times.
Number 2 found 2 times.
Number 3 found 1 times.
Number 4 found 3 times.
Number 5 found 1 times.
0 голосов
/ 21 апреля 2011

Почему вы используете 2-димный массив? Если известно, что ваши числа находятся в диапазоне 1..5, используйте индекс для числа: 

    int a[] = {1,4,1,5,2,2,4,3,4,1};
    int b[] = new int[5];

    for (int n : a)
        ++b[n-1];

    for (int j=0; j < 5; ++j)
        System.out.println (j + " is repeated " + b [j-1] + " times");
  • Не объявляйте переменные преждевременными и не используйте их повторно. Вы забудете удалить неиспользуемые переменные (count), и вам будет сложно анализировать код.
  • Используйте улучшенный цикл for:.
  • Объявите счетчики в голове - есть причина, почему это разрешено: для (int i = ...) и почему я не видим за пределами блока. Это не дорого. Нет, это не так. Посмотрите на байт-код.
...