我正在做过去的采访和一个问题陈述如下:学生被要求以非递减的顺序站立。找出没有站在正确位置的学生人数。
看起来很简单,但预期的输出完全不同,一些示例输出:
[5,1,1,3,4,1] -> 3
[4,1,2,3,4] -> 0
[4,4,3,2,1] -> 4
我看不到什么?
这里的想法是,您正在寻找具有降序顺序的子列表的总长度,以识别不在正确位置的学生(因为非降序的相反将按字面顺序降序)。降序也计算重复数,因此如果较大的数字位于相同数字中的两个之前,则该子列表也可以被认为是递减顺序。
以您提供的第一个列表为例。
[5, 1, 1, 3, 4, 1]
从上面看,第一个子列表序列是5, 1, 1
。由于5大于1,并且您在一个较大的数字后面有一系列1,因此列表按降序排列,并且有两个学生不按顺序排列。对于4和1来说,情况也同样如此。
最后一个列表有点棘手。
[4, 4, 3, 2, 1]
在这里,我们有一个学生在另一个排名第4的学生旁边排名第4位。正如我们已经建立的那样,如果我们在两个较小数字之前有一个较大的数字,那么列表可以按降序排列;但是,如果列表以相同的数字开头然后减少,则该子列表也按降序排列。
我们不计算领先4,因为他们在一个好的位置。如果这是2的列表,下面的4也将处于OK点。但是由于我们在第二个4之后添加了较小和较小的数字,我们确定第一个之后的每个元素都按降序排列,因此我们得到一个子列表长度为4。
这个问题措辞不好,所有这些答案都是基于意见的。那就是说,我唯一的想法是以任何合理的方式使这项工作是第一个数字表示数组的大小。
[5,1,1,3,4,1] -> 3
5名学生为了[1,1,3,4,1]
unsorted [1,1,3,4,1]
sorted [1,1,1,3,4]
non-matching [ x,x,x]
-> 3
其他人也一样
4名学生按顺序[1,2,3,4]
unsorted [1,2,3,4]
sorted [1,2,3,4]
non-matching [ ]
-> 0
4名学生按顺序[4,3,2,1]
unsorted [4,3,2,1]
sorted [1,2,3,4]
non-matching [x,x,x,x]
-> 4