Member 13192781 Ответов: 2

Мне нужно написать код, чтобы найти элемент в целочисленном массиве, который повторяется ровно " k " раз, но мой код не работает для огромного массива

Это точный вопрос от GeeksForGeeks.com

Цитата:
Задан массив из n целых чисел. Задача состоит в том, чтобы найти первый элемент, который встречается k раз. Если ни один элемент не встречается k раз, то выводится -1. Распределение целых элементов может быть в любом диапазоне.


Примечание:
Цитата:
Первая строка входных данных содержит целое число T, обозначающее количество тестовых случаев. Затем следуют T тестовых случаев. Первая строка каждого теста содержит целое число N, обозначающее размер массива, и число K. Вторая строка каждого теста содержит N целых чисел, разделенных пробелами, обозначающих элементы массива A[ ].


Что я уже пробовал:

Это мой код. Он не дает правильного вывода, когда размер массива равен 9383 и k = 6. Тогда он просто возвращает 0. Я хотел бы, чтобы вы помогли мне понять, где я, возможно, ошибся.

int FindRepeatedElement(vector<int>& nums, int k)
{
	sort(nums.begin(), nums.end());

	int count = 1, marked = 0;
	for (int i = 0; i < nums.size(); i++) // Here is a comparison
	{
		if (nums[i + 1] == nums[marked]) // Here is a comparison
		{
			count++;

			if (count == k) // Here is a comparison
				return nums[marked];
		}

		else
		{
			marked = i + 1;
			count = 1;
		}
	}
	return -1;
}

int main() {

	int t, n, k;
	
	
	cin >> t;

	while (t--)
	{
		cin >> n;
		cin >> k;
		vector<int> nums(n, 0);

		for (int i = 0; i < n; i++)
		{
			cin >> nums[i];
		}

		cout << FindRepeatedElement(nums, k) << endl;
	
	}

	system("pause");
	return 0;
}

0x01AA

Не то, что связано с вашей проблемой, но в любом случае проблема в вашем коде.
Существует вероятность того, что " индекс выйдет за пределы диапазона":
for (int i = 0; i < nums.size(); i++)
{
if (nums[i + 1] == nums[marked])

2 Ответов

Рейтинг:
2

OriginalGriff

Компиляция не означает, что ваш код верен! :смеяться:
Подумайте о процессе разработки как о написании письма: успешная компиляция означает, что вы написали письмо на правильном языке - например, на английском, а не на немецком, - а не то, что письмо содержало сообщение, которое вы хотели отправить.

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

Начните с рассмотрения того, что он делает и чем это отличается от того, что вы хотели. Это важно, потому что это дает вам информацию о том, почему он это делает. Например, если программа предназначена для того, чтобы позволить пользователю ввести число, а он удваивает его и печатает ответ, то если ввод / вывод был таким:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Тогда совершенно очевидно, что проблема заключается в бите, который удваивает его-он не прибавляет себя к себе или умножает его на 2, он умножает его на себя и возвращает квадрат входного сигнала.
Таким образом, вы можете посмотреть на код, и очевидно, что он где-то здесь:
private int Double(int value)
   {
   return value * value;
   }

Как только у вас появится идея, что может пойти не так, начните использовать отладчик, чтобы выяснить почему. Поставить точку останова на строке:
sort(nums.begin(), nums.end());

и запустите свое приложение. Подумайте о том, что должна делать каждая строка кода перед ее выполнением, и сравните это с тем, что она на самом деле делала, когда вы использовали кнопку "шаг вперед" для выполнения каждой строки по очереди. Он сделал то, что вы ожидали? Если да, то переходите к следующей строке.
Если нет, то почему? Чем это отличается?

Это навык, и его стоит развивать, поскольку он помогает вам как в реальном мире, так и в развитии. И, как и все навыки, он совершенствуется только при использовании!

Да, я, наверное, мог бы сказать вам, в чем "проблема" - но сделать это самому несложно, и при этом вы узнаете что-то действительно стоящее!

Рейтинг:
11

Patrice T

Цитата:
Он не дает правильного вывода, когда размер массива равен 9383 и k = 6.

Без хотя бы сокращенного набора данных почти невозможно угадать, что идет не так в вашем коде, даже если мы видим некоторые подозрительные вещи.
Цитата:
Он просто возвращает 0

Из вашего кода это означает, что целое число 0 - это ваш ответ. Вы проверили входные данные, если это правильный ответ ?

Проблема алгоритма в вашем коде:
Предположим, у вас есть {7, 7, 1, 0, 1, 0} и k=2, каков правильный ответ ? То, что это твое ?
Как видите, сортировка данных имеет побочные эффекты.

Как вам уже было сказано, используйте отладчик, чтобы увидеть, что делает ваш код.

0x01AA

Есть 5 для этого.

Patrice T

Спасибо

Member 13192781

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

Patrice T

Пожалуйста.