在geeksforgeeks.com提供的问题的背景下进行两次比较的含义 [英] Meaning of two comparisons in the context of the provided question from geeksforgeeks.com

问题描述

这是网站上的确切问题。



给定一个排序数组，其中包含10个元素，其中包含6个不同的数字，其中只重复1个数字五次。你的任务是仅使用两个比较找到重复的数字。



我不确定两个比较在这里意味着什么。你能否详细说明一下。谢谢。



我尝试了什么：



这是我的代码

  //   ConsoleApplication2.cpp：定义条目控制台应用程序的一个点。 
  //    
 
  #include     stdafx.h 
  
  #include   < span class =code-keyword><   iso646.h  >  
   #include   <   vector  >  
   #include < /跨度>  <   string   >  
   #include    <   iostream  >  
  
 
 使用 命名空间标准; 
 
  int  FindDuplicate（vector< int>& nums）
 {
 
  int  count =  1 ，标记=  0 ; 
 
  for （ int  i =  0 ; i< nums.size（）; i ++）
 {
 
  if （nums [i +  1 ] == nums [已标记]）
 {
 count ++; 
 
  if （count ==  5 ）
 返回 nums [已标记]; 
} 
 
  else  
 {
 marked = i +  1 ; 
 count =  1 ; 
} 
} 
 
 返回  0 ; 
} 

解决方案

Quote：

我不确定两个比较在这里意味着什么。

 使用  namespace  std; 
 
  int  FindDuplicate（vector< int>& nums）
 {
  int  count =  1 ，标记=  0 ; 
  for （ int  i =  0 ;  i< nums.size（）; i ++） //  这是一个比较 
 {
  if  （nums [i +  1 ] == nums [已标记]）  //  以下是比较 
 {
 count ++; 
 
 如果 （count ==  5 ）  //  以下是比较 
  return  nums [已标记]; 
} 
  else  
 {
 marked = i +  1 ; 
 count =  1 ; 
} 
} 
 返回  0 ; 
} 

假设向量包含重复5次的值，2次首次比较执行5到10次，第3次执行5次。对于此代码，总计在15到25之间进行比较。



您的代码检查值是否重复5次，然后才回答该值是什么值。你不会被要求检查重复值是否重复5次，这是一个知识。

你只是被要求找到哪一个。你可以进行2次比较。



[更新]

引用：

来自geeksforgeeks.com的问题

问题看起来像是一个小小的挑战，但仔细分析后，你会发现1比较足以知道答案。



[Chill60更新]

Chill60写道：

请把我的痛苦告诉我。

当然。你只需做一个视觉分析。

如果vector是 9 元素，它们看起来像：

1 1 1 1 1 2 3 4 5

1 2 3 4 5 5 5 5 5

  return  nums [ 4 ]; 

就是答案，不需要测试，因为元素4总是重复值。



如果vector是 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

 如果（nums [ 3 ] == nums [ 4 ]）
  return  nums [ 4 ];  //   nums {3]也是答案 
  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

由于数组已排序，因此必须将5个重复的数字组合在一起。

由于数组中只有10个元素，因此有3个场景可以找到这5个重复的数字：

1.在数组的前半部分;

2.在阵列的后半部分;或者

3.跨越阵列的中点！

分析并理解问题后，算法很明确：

 SET answer = index [4] //默认为中点，假设情景3 
 IF（index [0] == index [1]）那么//一个比较
 answer = index [0 ] 
 ELSE IF（index [8] == index [9]）那么//两个比较
 answer = index [8] 

< blockquote>我建​​议在哪里询问您是否从中获得了问题的网站，而不是与之无关的其他网站。



猜测 - 这就是全部，因为我们不再了解这个问题 - 你的代码只能进行两次测试：两个如果 s，两个 while s，或者一个用于，其中包含 if 。基本上，两个返回布尔结果的表达式。但我可能错了......

This is the exact question from the website.

Given a sorted array having 10 elements which contains 6 different numbers in which only 1 number is repeated five times. Your task is to find the duplicate number using two comparisons only.

I am not sure what "two comparisons" means here. Could you please shed some light on it. Thank you.

What I have tried:

This is my code

// 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;
}

解决方案

Quote:

I am not sure what "two comparisons" means here.

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;
}

Supposing the vector contain a value repeated 5 times, the 2 first comparisons are executed 5 to 10 times, the third is execute 5 times. Which total to between 15 to 25 comparisons for this code.

Your code is checking if a value is repeated 5 times before answering the value what is that value. You are not asked to check if there is a value repeated 5 times or not, this is a knowledge.
You are just asked to find which one. And you are allowed 2 comparisons.

[Update]

Quote:

question from geeksforgeeks.com

The question look like a little challenge, but with a careful analyze, you can find that 1 comparison is enough to know the answer.

[Update for Chill60]

Chill60 wrote:

Put me out my misery please.

Sure. You just have to do a visual analyze.
if vector is 9 elements, they look like:
1 1 1 1 1 2 3 4 5
1 2 3 4 5 5 5 5 5

return nums[4];

is the answer, no test required, because element 4 is always in repeated value.

if vector is 10 elements, they look like:
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];

if test fails, element 8 is the answer.
The same answer fits to vector size up to 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

Since the array is sorted, the 5 duplicate numbers must be grouped together in the array.
Since there are only 10 elements in the array, there are 3 scenarios where these 5 duplicate numbers can be located:
1. On the first half of the array;
2. On the second half of the array; or
3. Spanning across the midpoint of the array!
Having analyzed and understand the problem, the algorithm is clear:

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]

I'd suggest that the place to ask if the site you got the question from, rather than a different website that has no connection with it.

At a guess - and that's all it can be since we know no more about the question than you do - your code can have two tests only: two ifs, two whiles, or maybe one for with an if inside it. Basically, two expressions which return a boolean result. But I could be wrong...

这篇关于在geeksforgeeks.com提供的问题的背景下进行两次比较的含义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！