Количество различных элементов массива

[Serge_Bliznykov]

попробуйте такой код:

#include <iostream>
#include "fstream"
using namespace std;

int different_numbers(int n, int *a) {
	int i, j, kol = 1;
	for (i = 0; i<n - 1; i++) {
		if((i>0)&&(a[i]==a[0])) continue;
		for (j = i + 1; j<n; j++) {
			if (a[i] == a[j]) { a[j]=a[0]; break; }
		}
		if (j == n) kol++;
	}
	return kol;
}
int main() {
	int n, i, kol;
	ifstream f("input.txt");
	ofstream f1("output.txt");
	f >> n;
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++)
		f>> a[i];
	kol=different_numbers(n, a);
	f1<< kol;
 
	return 0;
}

p.s. эта попытка реализации той же самой идеи, что предложил evg_m - исключить поиск для элементов, которые ранее были найдены, как неуникальные.

[ShuricFC]

К сожалению не помогло.
Не подскажите, а этот код как оптимизировать? Может так работать будет быстрее.

#include <iostream>
#include "fstream"
using namespace std;
 
 
int main()
{
    ifstream f("input.txt");
    ofstream f1("output.txt");
    int i, n, j, kol = 1;
    f>> n;
    int* a;
    a = new int[n];
    for (i = 0; i < n; i++) {
        f>> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                
            }
 
        }
    }
    kol = n > 0 ? 1 : 0;
    for (i = 1; i < n; i++)
        if (a[i] != a[i - 1])
            kol++;
    f1 << kol;

[Serge_Bliznykov]

К сожалению не помогло.

ну, тогда я пас...

[ura_111]

Похоже evg_m уже писал об этом (в п.1), но у тебя нет никакой реакции на этот счет, - а ведь это важно! Это может существенно ускорить работу программы (я продублирую) ...

В настройках моего компилятора есть возможность оптимизации кода либо по объёму, занимаемой в памяти программы, либо по скорости работы этой самой программы. Понимаешь, есть обратная связь память/скорость.

34.jpg

А теперь к твоей программе: когда выделяешь динамическую память ("a = new int[n];") под данные ты явно (может не осознанно) пытаешься экономить оперативную память компьютера (в ущерб быстродействию), т.к. выделяешь её строго под данные - ни одного байта больше. А ты хоть знаешь сколько времени эта операция осуществляется?...

Может лучше использовать статическое резервирование памяти под массив: "int a[100]", "int a[1000]", "int a[10000]".... Посмотри какая расточительность памяти компьютера. Класс, ведь чем больше займешь памяти - тем быстрее будет работать программа (помнишь выше изложенную закономерность).

[evg_m]

если уж не хотите делать ВТОРОЙ массив, то могу предложить другую идею.

уменьшить длину просмотра для поиска уникальных.
Для этого собИрать все уникальные в начало.

unique:=0; //вначале уникальных нет (нет есть! первый(нулевой) всегда уникален)
for i:=unique+1 to n do
  // далее ПРОВЕРЯЕМ НАЧАЛО(уже просмотренные) списка на наличие 
  noignore:=-1;
  for j:=0 to unique do 
     if a[i]=a[j] then begin noignore:=j; break; end;

  if  noignore>=0 then begin //АГА встретили новый
    unique:=unique+1; a[unique]:=a[noignore];
  end;
end;

P.S. это конечно же не С, но ...

Да, и на массиве с большим числом неповторяемости вряд ли пройдет тесты.

[ShuricFC]

Всем большое спасибо! Проблема решена!

[Serge_Bliznykov]

Сообщение от ShuricFC

Всем большое спасибо! Проблема решена!

ну и как решена? Расскажите, любопытно же!

[ShuricFC]

Помогла быстрая сортировка и один проход по циклу.

[Serge_Bliznykov]

Сообщение от ShuricFC

Помогла быстрая сортировка и один проход по циклу.

Это удивительно - на сортировку должно уходить больше времени, чем на простой перебор, но, раз у Вас всё получилось, то поздравляю!

[New man]

У тебя сложность n^2 в начальном варианте. То есть, ты за O(n) выбираешь первые элементы, а потом за O(n) ищешь его копии. Это медленно.

Вариант с быстрой сортировкой лучше, так как ты сортируешь за O(n log n), а потом за O(n) ищешь числа. В итоге получается O(n log n).

Есть такой вариант, он лучше всего, так как там нет утечки памяти, как у тебя, да и работает он за O(n), так как проверка наличия и добавление элементов в хэш-таблицу работает за константу:

#include <unordered_set>
...

        f >> n;
	std::unordered_set<int> uniq, not_uniq;
	for (int i = 0; i < n; i++){
                int tmp;
		f>> tmp;
                if(uniq.find(tmp)!=uniq.end())// неуникальное число
                {
                     uniq.erase(tmp);
                     not_uniq.insert(tmp);
                }
                if(not_uniq.find(tmp)==not_uniq.end()){ // уникальное число
                      uniq.insert(tmp)
                }
        }
	
        f1<<uniq.size();
 
	return 0;