Как я могу удалить дубликаты из ответа во время выполнения O (n)? - PullRequest
Новая
       45

Как я могу удалить дубликаты из ответа во время выполнения O (n)?

2 голосов
/ 13 марта 2011 
void findodd(int a[])
{
  int hash[100];
  int i;
  int c[100]={0};
  for(i=0;i<6;i++)
  { 
    c[a[i]]=c[a[i]]+1;
    hash[a[i]]=c[a[i]];
    if(c[a[i]]%2==0)
      hash[a[i]]=0;
  }
  for(i=0;i<6;i++)
    if(hash[a[i]]!=0)
      cout<<a[i];
}
int main()
{
  int a[] = {1,3,3,5,5,5};
  findodd(a);
  return 0;
}

Программа должна найти целые числа, которые встречаются в массиве нечетное количество раз. Вот ссылка на вышеуказанную программу.

Ответы [ 3 ]

2 голосов
/ 14 марта 2011

Учитывая, что ваш алгоритм уже работает на O (n), я предполагаю, что вы хотите стереть дублирующиеся записи в выходных данных. Одно из возможных решений: 

void findodd(int a[])
{
  int hash[100];
  int i;
  int c[100]={0};

  int hashdup[100];
  memset(hashdup, 0, sizeof(int)*100);

  for(i=0;i<6;i++)
  { 
    c[a[i]]=c[a[i]]+1;
    hash[a[i]]=c[a[i]];
    if(c[a[i]]%2==0)
      hash[a[i]]=0;
  }
  for(i=0;i<6;i++)
  {
    if(hash[a[i]]!=0)
      hashdup[a[i]]++;
    if (hashdup[a[i]]==1)
      cout<<a[i];
  }
}
1 голос
/ 14 марта 2011 
#include <iostream>

void find_odd(int a[])
{
    int hash[101] = { 0 };
    int i;
    for( i = 0 ; i < 6 ; i++ )
    { 
        hash[ a[i] ]++;
    }

    for(i=0 ; i<100 ; i++)
        if(hash[i] != 0 && !(hash[i] % 2 == 0))
            std::cout << i << std::endl;    
}

int main()
{
    int a[] = {1,3,3,5,5,5};
    find_odd(a);
    return 0;
}

Но вам лучше использовать std::vector и / или std::map.

С негативами: но только в диапазоне -100 -> +100. Вы не можете иметь отрицательный индекс массива, поэтому просто +100 для всех и иметь массив hash от 0 до 200. 

#include <iostream>

void find_odd(int a[])
{
    int hash[201] = { 0 };
    int i;
    for( i = 0 ; i < 9 ; i++ )
    { 
        hash[ a[i]+100 ]++;
    }

    for(i=0 ; i<201 ; i++)
        if(hash[i] != 0 && !(hash[i] % 2 == 0))
            std::cout << i-100 << std::endl;    
}

int main()
{
    int a[] = {-1 , -1 , -1 , 1 , 3 , 3 , 5 , 5 , 5};
    find_odd(a);
    return 0;
}

С std::vector и std::map (работает как для положительных, так и для отрицательных чисел) 

#include <iostream>
#include <map>
#include <vector>

void find_odd_mapped(std::vector<int>& a)
{
    std::map<int , int> hash;
    std::map<int , int>::iterator map_iter;
    std::vector<int>::iterator vec_iter;

    for( vec_iter = a.begin() ; vec_iter != a.end() ; ++vec_iter )
        ++hash[*vec_iter];


    for(map_iter = hash.begin() ; map_iter != hash.end() ; ++map_iter)
        if(!((*map_iter).second % 2 == 0))
            std::cout << (*map_iter).first << std::endl;
}

int main()
{
    std::vector<int> a;
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(1);
    a.push_back(3);
    a.push_back(3);
    a.push_back(5);
    a.push_back(5);
    a.push_back(5);
    find_odd_mapped(a);
    return 0;
}
0 голосов
/ 14 марта 2011

единственное замечание: если вы знаете границы для ваших записей или нет, если есть ограниченные типы ввода, тогда все коды, указанные выше, будут работать, но если вы не знаете границы или если границы слишком высоки (дляНапример, у вас есть целочисленный диапазон записей), тогда даже лучший алгоритм использует O (nlogn) для удаления дублирующих записей.

...