不知道数组长度如何找到数组的中间值

Question

不知道数组长度如何找到数组的中间值

c++carraysstring

4

找出一个长度未知的字符串或数组的中间位置。您可能不能遍历列表以找到长度。您可能不使用任何内容来帮助您找到长度，因为它是“未知的”。（即没有sizeof（C）或count（C#）等 ...）

我在面试时被问到了这个问题。我只是想知道答案是什么。我问他是否可以使用sizeof，他说“不行，字符串或数组的大小未知 - 您只需要到达中间部分。”

顺便说一下，我不确定是否实际上可以不遍历就解决这个问题。我几乎感觉他可能想看看我对答案有多自信：S不确定...

他的英语很糟糕 - 我也不确定这是否导致了误解。他直接告诉我，我不需要遍历列表就能到达中间:S:S我假设他的意思是根本不需要遍历.....:S

- BigBug

7

除非你能够“寻求”到最后，否则这是不可能的。 - cnicutar

3

您在描述数据结构时使用了“字符串”、“数组”和“列表”的不同术语。请问这个数据结构确切是什么，以及它支持哪些有效操作？ - Robᵩ

2

这周有几个人面试同一个职位吗？我确定几天前已经提到过，但是我找不到第一次提到的内容了。 - mu is too short

6

数组或字符串的中间是 r :) - Saeed Amiri

2

如果你只知道段落的开头，就无法找到中间部分。想象一下你站在一个开阔的田野上，我告诉你向某个方向走一半；你应该怎么做？这里的开阔田野指的是计算机内存。 - Paul Manta

显示剩余2条评论

6个回答

5

您（或者面试官）在数据方面表述含糊不清，只提到了"string"和"array"，这个问题可以是任何东西。
您提到字符串的长度未知，但从您的措辞中似乎是指不可知。

a) 如果只是未知，那么问题在于如何确定？对于字符串来说，例如，您可以将其结束字符设为'\0'。然后可以应用其他答案所建议的一些算法。

b) 如果是不可知的，那么谜题就没有解答。没有开头和结尾的中间概念就没有意义。

总之，没有起点和终点，或长度，就不能谈论中间。这个问题要么故意无法回答，要么您没有理解它。您必须知道更多关于内存段的信息，而不仅仅是开头和类型。

- Paul Manta

+1 给予反对票没有理由（不是因为答案不好，而是我只有一票）。 - justin

2

从技术上讲，一个程序“不知道”数组的大小是不可能的，而字符串或列表的整个目的就是遍历它。唯一正确的答案是：问题本身就是错误的。面试官应该没有通过面试。 - wildplasser

2

以下代码将在不遍历列表的情况下找到数组的中间值。

int thearray[80];
int start = (int)&thearray;
int end = (int)(&thearray+1);
int half = ((end-start) / 4)/ 2;
std::cout <<  half << std::endl;

编辑：

这段代码假设你正在处理一个真正的数组，而不是指向其第一个元素的指针，因此像下面这样的代码：
int *pointer_to_first_element = (int *)malloc(someamount);
将无法工作，同样地，任何将数组引用降级为指向第一个元素的指针的表示法都不会起作用。基本上，任何使用 * 的表示法都不行。

- Serdalis

如果thearray是一个大小为4的实际对象数组，而不是指向其中一个元素的指针，那么这将起作用。 - Dennis Zickefoose

我将thearray初始化为thearray [80]，得到结果为40。你是对的，关于指向第一个元素的指针，但这是唯一可用的方法，将遵守“无遍历”规则，并且sizeof（int）可以是任意值，因为它只是一个硬编码数字。 - Serdalis

你确定吗？http://codepad.org/pWRYSkw8 顺便说一句，如果thearray的类型是char*，则end - start = 1。 - BlackBear

@keith 我正在将引用转换为整数，并且对它们不执行任何算术运算，只有生成的整数。&thearray 将是数组内存开始地址的引用，&thearray+1 将是该数组后面第一个地址的引用。我知道这是一个非常特殊的情况，但它确实存在，并且是唯一符合所有规则的情况。 - Serdalis

@Keith 我明白你的意思，你是正确的，这段代码做了很多假设，并假定了一个完美的环境。除了显而易见的情况外，我不知道它何时会失败，因为我没有足够的知识。 - Serdalis

显示剩余7条评论

0

你只需要使用第一个和最后一个元素的地址之间的差异。

- justin

2

你如何知道最后一个元素的地址？ - nhed

1

经过一番搜索，我现在明白了面试官的问题后来添加了限制条件，并且这一点在另一个答案的二十条评论中得到了说明。它也被标记为C++；C++类型具有可用于获取前端和后端元素地址的方法和迭代器。尽管如此，它仍然优于遍历，并且比被接受的答案更符合要求 ;) - justin

2

@anonymous_downvoter，这并没有帮助，除非你能解释一下你的行为。 - justin

我不同意......事实上，有些类型可以报告其大小是无关紧要的，如果您使用该功能，则忽略了问题的要求。我也不喜欢接受的答案（虽然没有对任何东西进行投票），我认为问题的措辞有些问题，可能试图简化T＆H问题，但它弄糟了。我最喜欢保罗的答案。 - nhed

当然，如果已知第一个和最后一个元素，该技术也可以应用于C数组。我不觉得我的答案是错误的，因为我没有找到所有复活节彩蛋要求，那样做很傻。继续说：在这种情况下，T＆H是一种较差的解决方案，因为它1）还依赖于知道最后一个元素，并且2）使用遍历来确定中间值。前者是一个复活节彩蛋要求（再次，没有同情）。后者在计算上劣于我的解决方案，并且有争议地未能满足另一个正式要求（无遍历）。 - justin

显示剩余4条评论

-1

我认为这个问题旨在测试您的问题分析和需求收集技能。正如其他人之前所说，我们需要至少另一条数据来解决这个问题。

我的方法是让面试官清楚地知道，我们可以通过函数调用中的一个约束条件来解决问题：调用者必须提供两个指针，一个指向数组的开头，另一个指向数组的结尾。给定这两个指针，并使用基本的指针算术，我得出了这个解决方案；请告诉我您对此的看法。

int *findMiddleArray( int const *first, int const *last )
{
  if( first == NULL || last == NULL || first > last )
  {
    return NULL;
  }
  if( first == last )
  {
    return (int *)first;
  }
  size_t dataSize= ( size_t )( first + 1 ) - ( size_t )first,
         addFirst= ( size_t )first,
         addLast=  ( size_t )last,
         arrayLen= ( addLast - addFirst) / dataSize + 1,
         arrayMiddle= arrayLen % 2 > 0 ?  arrayLen / 2 + 1 : arrayLen / 2;

  return ( int * )( ( arrayMiddle - 1 ) * dataSize + addFirst );
}

- stdcode

-2

找到数组中点的一种方法是（对于奇数长度的数组），只需使用两个循环，第一个循环从0索引开始遍历，另一个嵌套的循环将从数组的最后一个索引开始遍历。现在只需比较元素，当它们相同时...那就是数组的中点。即如果(arr[i]== arr[j])。希望你明白了！

对于偶数长度的数组...你可以这样做if(arr[i] == arr[j-1]) 或者 if(arr[i] == arr[j+1]) 因为它们永远不会相同。通过干运行试试吧！

- Salman Hayat

2

只有当所有数组值都是唯一的时，此方法才有效。例如，如果第一个和最后一个元素具有相同的值，则循环会立即停止。 - Blastfurnace

3

问题说明数组的长度是未知的，因此不能仅使用数组的最后一个索引，因为其是未知的。 - Olov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Brunt · Accepted Answer

有两个计数器c1和c2。开始遍历列表，每次增加c1一次，每隔一次增加c2一次。当c1到达末尾时，c2将在中间位置。

你没有“遍历列表来查找长度”，然后将其除以二，你只是通过一次循环完成了这个过程。

我所能想到的另一种方法就是不断地取走列表的第一个和最后一个项目，直到只剩下中间的一个或几个项目。