Массив из неповторяющихся чисел

Question

Массив из неповторяющихся чисел

Рейтинг: -1Ответов: 1Опубликовано: 26.04.2015

Здравствуйте, у меня задание создать массив из рандомных чисел, а после создать новый в котором будут только неповторяющиеся числа из старого массива. Я вроде написал все правильно...... Но в массиве C выходят огромные числа. Подскажите пожалуйста, где может быть ошибка.

#include "stdafx.h"
#include <stdio.h>
#include <clocale>
#include <windows.h>
#include <math.h>
#include <iostream>
#include <time.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    srand (time(NULL));
    int j=0,t=0,N,i=0,e;
setlocale(0, "Russian");

cout<<"______________"<<endl<<"Введите размер массивов N=";
cin>>N;
cout<<endl;
int A[100], B[100], C[100];

//первый массив
for(i=0;i<N;i++)
{
     A[i]=rand()%100;
}
cout<<endl<<"Введите число колонок массива А:";
cin>>e;
cout<<endl;
cout<<"Массив A:"<<endl<<endl;
for(i=0;i<N;i++)
{
    cout<<A[i];
    if((i+1)%e) cout<<"\t";
    else        cout<<"\n";
}
//алгоритм
for(j=0;j<N;j++)
{
    for(i=i+1;i<N;i++)
    {
        if (j==A[i]) t++;

    }
    if (t=0) C[i-1]=j;
    t=0;
}
//второй массив
cout<<endl<<"Введите число колонок массива C:";
cin>>e;
cout<<endl;
cout<<"Массив C(без повторов):"<<endl<<endl;
for(i=0;i<N;i++)
{
    cout<<C[i];
    if((i+1)%e) cout<<"\t";
    else        cout<<"\n";
}
    return 0;
}

c# массивы сортировка

Источник: Stack Overflow на русском

Answer 1

▲ 5Принят

Ошибка номер раз:

for(j=0;j<N;j++)
{
    for(i=i+1;i<N;i++)

Очевидно, имелось в виду:

for(j=0;j<N;j++)
{
    for(i=j+1;i<N;i++)

Ошибка номер два:

if (t=0) C[i-1]=j;

Обе они приводят к тому, что массив C[] не заполняется вообще. А поскольку он не инициализирован, то и выводится всякий мусор из стека, который в нём содержится.

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

Со второй: включите ВСЕ предупреждения в компиляторе и не игнорируйте их. Например, gcc -Wall скажет:

warning: suggest parentheses around assignment used as truth value
         if (t=0) C[i-1]=j;
         ^

Какие-то компиляторы сообщат, что "assignement found in boolean expression", и т.д.

Плюс - использовать "нотацию Йоды". Такая конструкция просто не скомпилируется:

if (0=t) C[i-1]=j;

Но это ещё не всё. После исправления этих ошибок правильно работать программа не станет. Потому что есть проколы и в алгоритме поиска, и при выводе результирующего массива. Вот так - работает:

for( j = 0; j < N; j++ )
{
    int c = 0;
    for( i = 0; i < N; i++ )
    {
        if( A[i] == A[j] &&  i != j )
        {
            c = 1;
            break;
        }
    }
    if( !c ) C[t++] = A[j];
}
for( i = 0; i < t; i++ )  // ограничение - не N!
{
    std::cout << C[i] << " ";
}

Но нужно учитывать, что сложность такого алгоритма достаточно высока и на больших объёмах он будет работать долго. Как вариант:

inline static int
compareInt( const void * a , const void * b )
{
    return *(int*)a - *(int *)b;
}

/* ... */
qsort( A, N, sizeof(A[0]), compareInt );
for( i = 0; i < N; i++ )
{
    if( i && A[i] == A[i-1] ) continue;
    if( i != N && A[i] == A[i+1] ) continue;
    C[t++] = A[i];
}
// Всё!

Смысл вот в чём. Сначала мы сортируем массив. Потом делаем по нему всего один проход, сравнивая каждый элемент с соседом слева и справа (для i = 0 исключаем первое сравнение, для i = N второе). Если соседи не равны нашему элементу - он уникальный, сохраняем его в C[].

Ещё вариант. До памяти жручий в случае большого разброса значений, но шустрый.

int t, i, min, max;

// Сначала нужно создать массив, в котором будем хранить
// счётчики ВСЕХ возможных значений исходного массива.
// Конечно, раз уж речь о C++, то можно (и даже нужно) 
// использовать стандартный плюсовый хэш вместо сишного массива.
// Но попробуем и так.
// Для начала ищем минимальный и максимальный элементы.
min = max = A[0];
for( i = 1; i < N; i++ )
{
  if( A[i] < min ) min = A[i];
  if( A[i] > max ) max = A[i];
}

// В t - размер массива для сохранения значений.
// Тут небольшая плюшка в случае отрицательных значений, но для
// краткости кода просто не будем касаться этого варианта.
t = max - min + 1;
C = new int[t];

// Теперь просто проходимся по исходному массиву и 
// увеличиваем счётчик для каждого значения, отсчитывая базу от min:
for( i = 0; i < N; i++ )
{
  C[A[i]-min]++;
}

// Если счётчик больше 1 - значение не уникально,
// если 1 - уникальное, выводим (или делаем что-то ещё),
// не забываем прибавить базу:
for(i = 0; i < t; i++ )
{
    if( C[i] == 1 )
    {
        std::cout << (i + min) << " ";
    }
}
delete [] C;

А теперь то же самое, но на "чистом" C++:

std::map<int,size_t> C;
for( size_t i = 0; i < N; i++ )
{
  C[A[i]]++;
}
for(size_t i = 0; i < C.size(); i++ )
{
    if( C[i] == 1 )
    {
        std::cout << i << ' ';
    }
}

P.S. Ну не могу удержаться, последний алгоритм - на перле, причём для любых скаляров:

my @A = ( 1,2,'b',4,5,6,'a',8,3,'a',6,9,2 );
my %C;
$C{$_}++ for @A;
$C{$_} == 1 && print "$_\n" for keys %C;
# Всё :-)

Массив из неповторяющихся чисел

Ответы