在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: twoif
s, twowhile
s, or maybe onefor
with anif
inside it. Basically, two expressions which return a boolean result. But I could be wrong...
这篇关于在geeksforgeeks.com提供的问题的背景下进行两次比较的含义的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!