Найти не повторяющиеся числа в массив целых чисел


Программа находит не повторяющееся число в инт массива. Я использую рассчитывать на дубликаты и делает Numcounts[] для сохранения значения подсчета. Я предполагаю, что массив не будет отсортирован. Затем я могу проверить Numcounts[] на 1, и что бы не повторяющийся номер. Сложность \$o(п^2)\$.

Можете ли вы сказать мне, как сделать то же самое с использованием всех HashMap? Я не использовал всех HashMap и я знаю, что сложность может быть уменьшена до \$О(П))\$ используя их.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    int n=6;
    int * Numcounts = new int[n];
    int count = 0;
    int a[6] = {1,1,1,2,2,3}; // sort the array before proceeding.Because in the else part count is set to zero. 
    //If the array is unsorted then count will be reset in middle and will not retain the previous count.
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==a[j])
            {
                count = count+1;
                Numcounts[i] = count;
            }
            else{
                count = 0;
            }
        }
    }
}


27681
7
задан 24 марта 2011 в 07:03 Источник Поделиться
Комментарии
4 ответа

Если массив отсортирован, вам не нужно всех HashMap, чтобы достичь o(n) времени. Если у вас есть случайный/массив несортированный вы можете использовать всех HashMap для достижения цели, ответ Паулу за это. Обратите внимание, что сортировка требует o(n журнал(N)).

Если вы хотите знать, как часто каждое число в исходной коллекции, вам также понадобится всех HashMap, но если вы только хотите знать, в неповторяющихся числа в отсортированном массиве следующий код будет работать:

// N is the number of ints in sorted
int nonduplicate(int sorted[], const int N){
//To prevent segfaulting when N=1
if(N==1){ return sorted[0]; };

for(int i=0;i < N-1;i++){
if(sorted[i] == sorted[i+1]){
// Next number in collection is the same so the current number is not unique
// Set i to the first location of the next different number
do{
i++;
}while(i < N-1 && sorted[i] == sorted[i+1]);
}else{
// The next number is different so the current is unique
return sorted[i];
}
}
// Is the last number unique?
if(sorted[N-1] != sorted[N-2]){
return sorted[N-1];
}
// No unique numbers
return -1; // Or some other value you reserve for it
}

Обратите внимание, что этот код выполняется быстрее, потому что он не имеет накладных расходов в HashMap и может остановиться до пересечения весь массив, но имеет же большую-o предел.

7
ответ дан 24 марта 2011 в 08:03 Источник Поделиться

Поскольку вы используете C++, а не c, есть несколько вещей, которые вы могли бы очистить.

Во-первых, в коде утечек памяти: вы новыйИнг памяти, но вы не удалитьинж. Для того, чтобы избежать ручного управления памятью, вы должны использовать СТД::вектор шаблона класса вместо нового[].

Кроме того, с stdio.ч это наследие с заголовка. Использовать с cstdio с++. Но на самом деле, ваш код не нужен заголовок.

Хэш-карту реализации в функции std::ТР1 пространства имен. Если ваш компилятор поддерживает это (современные компиляторы делают), следующий код работает:

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
std::unordered_map<int, unsigned> occurrences;
int a[6] = { 1, 1, 1, 2, 2, 3 };
unsigned const size = sizeof a / sizeof a[0];

// First pass: count occurrences.
for (unsigned i = 0; i < size; ++i)
++occurrences[a[i]];

// Second pass: search singleton.
for (unsigned i = 0; i < size; ++i)
if (occurrences[a[i]] == 1)
std::cout << a[i] << " only occurred once." << std::endl;
}

(Для включения ТР1 поддержку на ССЗ, пройти с std=с++0х флаг для компилятора.)

Точки интереса: первый проход работает, потому что значения внутри неупорядоченного карту (= хэш-карта) инициализируются со значением по умолчанию 0. Мы используем этот факт для приращения ценности непосредственно не удосужившись проверить, является ли значение существует в карте заранее. Это делает код более кратким и более эффективным.

4
ответ дан 25 марта 2011 в 04:03 Источник Поделиться

Хеш-это структура, которая отображает ключ (хэш) значение.
В вашем примере, вы хотите ключ к число и значение подсчет каждого номера.
Если вы используете компилятор, который поддерживает C++0х, вы можете добавить

#include <unordered_map>

а затем изменить тело вашей основной цикл, что-то вроде:

std::unordered_map<int, int> hashMap;
for(int i=0;i<n;i++)
{
int number = a[i];

// check if this number is already in the map
if(hashMap.find(number) != hashMap.end())
{
// it's already in there so increment the count
hashMap[number] += 1;
}
else
{
// it's not in there yet so add it and set the count to 1
hashMap.insert(number, 1);
}
}

Я написал этот код из памяти, так что он может даже не компилироваться, хотя это должно быть просто исправить.

Как вы видите, мы только один раз запустить через массив, так что теперь у вас есть о(n) сложности.

3
ответ дан 24 марта 2011 в 07:03 Источник Поделиться

На самом деле, вы могли бы сделать это в \$О(П)\$ с помощью операции XOR с битовым сдвигом вещи.

Это позволит сделать это с меньшими затратами и намного быстрее (в Java, так это то, что я знаю):

public static void main(String... args) {
int[] x = new int[] { 5,7,4,9,5,7,4 };
int result = 0;
for (int i=0;i<x.length;i++) {
result ^= x[i];
}
System.out.println("result:"+result);
}

Хорошая статья об этом здесь: http://kaipakartik.amplify.com/

3
ответ дан 22 июня 2011 в 05:06 Источник Поделиться