简单但令人困惑的算法问题 [英] Simple but confusing algorith question

问题描述

嘿所有，

我最近在一次采访中被问到这个问题：


假设你有方法签名


bool MyPairSum（int [] array，int sum）


数组有所有唯一值（无重复），你的任务是找到两个
$ b数组中的$ b索引，其总和等于输入参数sum。如果有
存在数组中的两个条目，它们总和相等于sum的输入

参数，则返回true，否则返回false。什么是

最有效的实现？


我的问题是我们能否有一个更好的O（n2）的更糟糕的案例运行时间

我想在最糟糕的情况下，你必须将每个指数

与所有其他指数进行比较并测试每个总和，直到找到一个

匹配输入总和。在更糟糕的情况下，将没有一对

索引等于输入和参数。我是否会忽略一个非常好的b $ b基本技巧？我想到这里所有尖锐的人，有人可以看到我是否离开基地是不是很好看。


这是'样本实现我在考虑：

bool MyPairSum（int [] array，int sum）

{

for（int i = 0; i < array.Length; i ++）

{

for（int j = i + 1; j< array.Length; j ++）

{

if（array [i] + array [j] == sum）

返回true;

}

}

返回false;

}

Tks，Karan S.

解决方案

如果数据已经排序，你可以做得更好。如果他们没有排序你

将有n ^ 2作为你最坏的情况，因为你必须检查每个值的

数组的每个索引。


即使这样你仍然可以通过在每次迭代中只发出一个add / sub

而不是一个操作来做得更好......参见示例。


bool MyPairSum（int [] array，int sum）

{

for（int i = 0; i< array.Length; i ++）

{

int need = sum - array [j];

for（int j = 0; j< array.Length; j ++ ）

{

if（array [j] == sum）

return true;

}

}

返回false;

}


此外，您的代码有失败模式，因为int j = i + 1 ......

下面的数据怎么样？


数组0,1,2 sum = 3使用i + 1你说它没有'不存在。


另一个快速的问题......下面的行为应该是什么？


数组1,2,3， 4 sum = 5


干杯，


格雷格


< ka ******** **@gmail.com>在消息中写道

新闻：11 ********************* @ i39g2000cwa.googlegro ups.com ...

嘿所有，

我最近在一次采访中被问到这个问题：


假设你有方法签名


bool MyPairSum（int [] array，int sum）


数组有所有唯一值（无重复），你的任务是找到两个
$ b数组中的$ b索引，其总和等于输入参数sum。如果有
存在数组中的两个条目，它们总和相等于sum的输入

参数，则返回true，否则返回false。什么是

最有效的实现？


我的问题是我们能否有一个更好的O（n2）的更糟糕的案例运行时间

我想在最糟糕的情况下，你必须将每个指数

与所有其他指数进行比较并测试每个总和，直到找到一个

匹配输入总和。在更糟糕的情况下，将没有一对

索引等于输入和参数。我是否会忽略一个非常好的b $ b基本技巧？我想到这里所有尖锐的人，有人可以看到我是否离开基地是不是很好看。


这是'样本实现我在考虑：

bool MyPairSum（int [] array，int sum）

{

for（int i = 0; i < array.Length; i ++）

{

for（int j = i + 1; j< array.Length; j ++）

{

if（array [i] + array [j] == sum）

返回true;

}

}

返回false;

}

Tks，Karan S.

< blockquote>这是排序

数组1,2,3,4总和= 5


这不是排序

数组1 ，4,2,3 sum = 5


哪一个更快？


SA


Greg Young [MVP]" <博士************* @ hotmail.com>在消息中写道

新闻：OM ************* @ TK2MSFTNGP05.phx.gbl ...

如果数据已经排序了你可以做得更好。如果他们没有排序
你将有n ^ 2作为最糟糕的情况，因为你必须检查每个值的
数组的每个索引。

甚至所以你仍然可以通过在每次迭代中只发出一个
add / sub
代替操作来做得更好......参见示例。

bool MyPairSum（int []数组，int sum）
{
for（int i = 0; i< array.Length; i ++）
{int / need = sum - array [j];
for（int j = 0; j< array.Length; j ++）
{
if（array [j] == sum）
return true;
}
}
返回false;
}

你的代码也有故障模式，因为int j = i + 1 ...
以下数据怎么样？数组0,1,2总和= 3使用i + 1你说它不存在。

另一个快速的问题......应该怎么做是为了以下几点？

阵列1,2,3,4总和= 5
欢呼，

Greg
< ka ********** @ gmail.c OM>在消息中写道
新闻：11 ********************* @ i39g2000cwa.googlegro ups.com ...
嘿所有，

我最近在一次采访中被问到这个问题：

假设你有方法签名

bool MyPairSum（int [] array，int sum）<数组具有所有唯一值（无重复），您的任务是在数组中找到两个
索引，其总和等于输入参数sum。如果存在
数组中的两个条目，它们总和相等于sum的输入参数，则返回true，否则返回false。什么是最有效的实施？

我的问题是我们可以有更好的O（n2）更糟糕的案例运行时间吗？
我在想更糟糕的情况是，你必须将每个指数与所有其他指数进行比较并测试每个总和，直到找到一个与输入总和匹配的指数。在更糟糕的情况下，将不存在等于输入和参数的一对
索引。我忽略了一个非常基本的伎俩吗？我想到了这里所有敏锐的人，有人可以辨别出我是不是基地了。

这是我想到的示例实现：

bool MyPairSum（int [] array，int sum）
{
for（int i = 0; i< array.Length; i ++）
{
for（int j = i + 1; j< array.Length; j ++）
{
if（array [i] + array [j] == sum）
return true;
}
}
返回false;
}

Tks，Karan S.

if（array [j] == sum）< ==需要

返回true;


" Greg Young [MVP]" <博士************* @ hotmail.com>在消息中写道

新闻：OM ************* @ TK2MSFTNGP05.phx.gbl ...

如果数据已经排序了你可以做得更好。如果他们没有排序
你将有n ^ 2作为最糟糕的情况，因为你必须检查每个值的
数组的每个索引。

甚至所以你仍然可以通过在每次迭代中只发出一个
add / sub
代替操作来做得更好......参见示例。

bool MyPairSum（int []数组，int sum）
{
for（int i = 0; i< array.Length; i ++）
{int / need = sum - array [j];
for（int j = 0; j< array.Length; j ++）
{
if（array [j] == sum）
return true;
}
}
返回false;
}

你的代码也有故障模式，因为int j = i + 1 ...
以下数据怎么样？数组0,1,2总和= 3使用i + 1你说它不存在。

另一个快速的问题......应该怎么做是为了以下几点？

阵列1,2,3,4总和= 5
欢呼，

Greg
< ka ********** @ gmail.c OM>在消息中写道
新闻：11 ********************* @ i39g2000cwa.googlegro ups.com ...
嘿所有，

我最近在一次采访中被问到这个问题：

假设你有方法签名

bool MyPairSum（int [] array，int sum）<数组具有所有唯一值（无重复），您的任务是在数组中找到两个
索引，其总和等于输入参数sum。如果存在
数组中的两个条目，它们总和相等于sum的输入参数，则返回true，否则返回false。什么是最有效的实施？

我的问题是我们可以有更好的O（n2）更糟糕的案例运行时间吗？
我在想更糟糕的情况是，你必须将每个指数与所有其他指数进行比较并测试每个总和，直到找到一个与输入总和匹配的指数。在更糟糕的情况下，将不存在等于输入和参数的一对
索引。我忽略了一个非常基本的伎俩吗？我想到了这里所有敏锐的人，有人可以辨别出我是不是基地了。

这是我想到的示例实现：

bool MyPairSum（int [] array，int sum）
{
for（int i = 0; i< array.Length; i ++）
{
for（int j = i + 1; j< array.Length; j ++）
{
if（array [i] + array [j] == sum）
return true;
}
}
返回false;
}

Tks，Karan S.

Hey all,
I was asked this question in an interview recently:

Suppose you have the method signature

bool MyPairSum(int [] array, int sum)

the array has all unique values (no repeats), your task is to find two
indices in the array whose sum equals the input parameter sum. If there
exists two entries in the array that sum together to equal the input
parameter of sum, then return true, otherwise return false. what''s the
most efficient implementation?

My question is can we have a better worse case runtime of O(n2) ??
I''m thinking that in the worse case, you''d have to compare each index
against all the other indices and test each sum until you find one that
matches the input sum. In the worse case, there will be no pair of
indices that equal the input sum parameter. Am I overlooking a very
basic trick? I figured with all the sharp people in here, somebody can
discern whether I''m off base or not :)

Here''s the sample implementation I was thinking of:
bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if ( array[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

解决方案

If the data were sorted you could do much better. If they are not sorted you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn''t exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@gmail.com> wrote in message
news:11*********************@i39g2000cwa.googlegro ups.com...
Hey all,
I was asked this question in an interview recently:

Suppose you have the method signature

bool MyPairSum(int [] array, int sum)

the array has all unique values (no repeats), your task is to find two
indices in the array whose sum equals the input parameter sum. If there
exists two entries in the array that sum together to equal the input
parameter of sum, then return true, otherwise return false. what''s the
most efficient implementation?

My question is can we have a better worse case runtime of O(n2) ??
I''m thinking that in the worse case, you''d have to compare each index
against all the other indices and test each sum until you find one that
matches the input sum. In the worse case, there will be no pair of
indices that equal the input sum parameter. Am I overlooking a very
basic trick? I figured with all the sharp people in here, somebody can
discern whether I''m off base or not :)

Here''s the sample implementation I was thinking of:
bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if ( array[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

This is Sorted
array 1,2,3,4 sum = 5

This is not Sorted
array 1,4,2,3 sum = 5

Which one is faster??

SA

"Greg Young [MVP]" <Dr*************@hotmail.com> wrote in message
news:OM*************@TK2MSFTNGP05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn''t exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@gmail.com> wrote in message
news:11*********************@i39g2000cwa.googlegro ups.com...
Hey all,
I was asked this question in an interview recently:

Suppose you have the method signature

bool MyPairSum(int [] array, int sum)

the array has all unique values (no repeats), your task is to find two
indices in the array whose sum equals the input parameter sum. If there
exists two entries in the array that sum together to equal the input
parameter of sum, then return true, otherwise return false. what''s the
most efficient implementation?

My question is can we have a better worse case runtime of O(n2) ??
I''m thinking that in the worse case, you''d have to compare each index
against all the other indices and test each sum until you find one that
matches the input sum. In the worse case, there will be no pair of
indices that equal the input sum parameter. Am I overlooking a very
basic trick? I figured with all the sharp people in here, somebody can
discern whether I''m off base or not :)

Here''s the sample implementation I was thinking of:
bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if ( array[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

if (array[j] == sum) < == need
return true;

"Greg Young [MVP]" <Dr*************@hotmail.com> wrote in message
news:OM*************@TK2MSFTNGP05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn''t exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@gmail.com> wrote in message
news:11*********************@i39g2000cwa.googlegro ups.com...
Hey all,
I was asked this question in an interview recently:

Suppose you have the method signature

bool MyPairSum(int [] array, int sum)

the array has all unique values (no repeats), your task is to find two
indices in the array whose sum equals the input parameter sum. If there
exists two entries in the array that sum together to equal the input
parameter of sum, then return true, otherwise return false. what''s the
most efficient implementation?

My question is can we have a better worse case runtime of O(n2) ??
I''m thinking that in the worse case, you''d have to compare each index
against all the other indices and test each sum until you find one that
matches the input sum. In the worse case, there will be no pair of
indices that equal the input sum parameter. Am I overlooking a very
basic trick? I figured with all the sharp people in here, somebody can
discern whether I''m off base or not :)

Here''s the sample implementation I was thinking of:
bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if ( array[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

这篇关于简单但令人困惑的算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！