Member 13192781 Ответов: 3

Значение двух сравнений в контексте поставленного вопроса из geeksforgeeks.com

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

Дан отсортированный массив из 10 элементов, содержащий 6 различных чисел, в которых только 1 число повторяется пять раз. Ваша задача состоит в том, чтобы найти дубликат числа, используя только два сравнения.

Я не совсем понимаю, что здесь означает "два сравнения". Не могли бы вы пролить на это немного света? Спасибо.

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

Это мой код
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iso646.h>
#include <vector>
#include <string>
#include<iostream>


using namespace std;

int FindDuplicate(vector<int>& nums)
{

	int count = 1, marked = 0;

	for (int i = 0; i < nums.size(); i++)
	{		

		if (nums[i + 1] == nums[marked])
		{
			count++;

			if (count == 5)
				return nums[marked];
		}

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

	return 0;
}

3 Ответов

Рейтинг:
24

Patrice T

Цитата:
Я не совсем понимаю, что здесь означает "два сравнения".

using namespace std;
 
int FindDuplicate(vector<int>& nums)
{
 	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 == 5) // Here is a comparison
				return nums[marked];
		}
 		else
		{
			marked = i + 1;
			count = 1;
		}
	}
 	return 0;
}

Предположим, что вектор содержит значение, повторенное 5 раз, 2 первых сравнения выполняются от 5 до 10 раз, третье выполняется 5 раз. Что в общей сложности составляет от 15 до 25 сравнений для этого кода.

Ваш код проверяет, повторяется ли значение 5 раз, прежде чем ответить на вопрос, что это за значение. Вас не просят проверить, есть ли значение, повторенное 5 раз или нет, это знание.
Вас просто просят найти, какой именно. И Вам разрешено 2 сравнения.

[Обновление]
Цитата:
вопрос от geeksforgeeks.com

Вопрос выглядит как небольшой вызов, но при тщательном анализе вы можете обнаружить, что 1 сравнения достаточно, чтобы знать ответ.

[Обновление для Chill60]
Chill60 писал:
Избавь меня от страданий, пожалуйста.

Конечно. Вам просто нужно сделать визуальный анализ.
если вектор есть 9 элементы, они выглядят как:
1 1 1 1 1 2 3 4 5
1 2 3 4 5 5 5 5 5
return nums[4];

это ответ, никакого теста не требуется, потому что элемент 4 всегда находится в повторяющемся значении.

если вектор есть 10 элементы, они выглядят как:
1 1 1 1 1 2 3 4 5 6
1 2 3 4 4 4 4 4 5 6
1 2 3 4 5 5 5 5 5 6
1 2 3 4 5 6 6 6 6 6
if (nums[3]==nums[4])
    return nums[4]; // nums{3] is also the answer
else
    return nums[8];

если тест провалится, ответом будет элемент 8.
Тот же ответ подходит для вектора размером до 13:
1 2 3 4 5 5 5 5 5 6 7 8 9
1 2 3 4 5 6 7 8 9 9 9 9 9

Member 13192781

Итак, сравнение просто означает, что я использую булев оператор для сравнения двух величин. В моем коде, поскольку я использовал цикл, я сравниваю одни и те же величины несколько раз и, следовательно, нарушил требование вопроса. В этом есть смысл. Большое вам спасибо за вашу помощь.

CHill60

Спасибо! Довольно элегантно. Я был слишком сосредоточен на сравнении nums[4] и nums[5], чтобы увидеть, что было прямо передо мной.

Patrice T

Спасибо

Рейтинг:
2

OriginalGriff

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

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

Member 13192781

Спасибо за вашу помощь. Я действительно ценю это.

Рейтинг:
15

Peter Leow

Поскольку массив отсортирован, 5 повторяющихся чисел должны быть сгруппированы вместе в массиве.
Поскольку в массиве всего 10 элементов, существует 3 сценария, в которых эти 5 повторяющихся чисел могут быть расположены:
1. на первой половине массива;
2. на второй половине массива; или
3. охват через среднюю точку массива!
Проанализировав и поняв проблему, алгоритм становится ясен:

SET answer = index[4] // midpoint by default, assuming scenario 3
IF (index[0]==index[1]) THEN // one comparision
    answer = index[0]
ELSE IF (index[8]==index[9]) THEN  // two comparision
    answer = index[8]

Member 13192781

Большое спасибо. Теперь я понимаю, что подразумевается под двумя сравнениями. Мой код использует несколько сравнений из-за цикла for и, следовательно, это неправильно.

Patrice T

Привет, Питер.
Вы видели, что 1 сравнения достаточно ?

CHill60

Ok @ppolymorphe - ты меня интригуешь.
Я вижу, что для любого паттерна требуется одно сравнение кроме где повторное число - это первые 5 или последние 5 записей. Я просто не вижу, как отличить эти 2 сценария без дальнейшего сравнения :(
Избавь меня от страданий, пожалуйста.

Patrice T

обновите мой ответ для вас.