当前位置：首页 → 问答吧 → 两道比较复杂的轩辕互动面试题(Python实现)

两道比较复杂的轩辕互动面试题(Python实现)

时间：2011-04-11

来源：互联网

1.平衡点问题
平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点
下面是代码：

1 li = [1,3,5,7,8,25,4,20]
2 def main():
3 i = 0
4 length = len(li)
5 before = 0
6 after = 0
7 mark = 0
8 balance = 0
9 total = sum(li)
10 while True:
11 balance = i + 1
12 if balance + 1 > length -1:
13 return -1
14 if li[i] == li[balance+1]:
15 mark = balance
16 return (mark,li[mark])
17 else:
18 before = before + li[i]
19 other = total - before - li[balance]
20 if before == other:
21 mark = balance
22 return (mark,li[mark])
23 i += 1
24 if __name__ == "__main__":
25 print main()

复制代码

2.支配点问题：
支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；
要求：返回任何一个支配点
本问题可归结为众数问题（统计学范畴），即一组数据中出现次数最多的那个数值，它可以没有也可以为多个。
下面是代码，如果你又更号的实现，不吝赐教。

1 li = [1,3,4,3,3]
2 def main():
3 mid = len(li)/2
4 for l in li:
5 count = 0
6 i = 0
7 mark = 0
8 while True:
9 if l == li[i]:
10 count += 1
11 temp = i
12 i += 1
13 if count > mid:
14 mark = temp
15 return (mark,li[mark])
16 if i > len(li) - 1:
17 break
18 else:
19 return -1
20 if __name__ == "__main__":
21 print main()

复制代码

最后，还有个一个中位数的问题，在很多笔试中也会遇到。
中位数：即数据从小到大排列，将数据分为两部分，一部分大于该数值，一部分小与该数值。中位数的位置是这样计算的：如果数据长度为奇数，中位数的位置为（N+1）/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。

作者: ysitbook 发布时间: 2011-04-11

第一个，貌似以数组中间的元素为分界，分别求两边的 subarray 的和，比较之后再决定将分界左移或者右移，然后重复求和和比较。这样应该更快一些。

后面的一个，如果先对数据做个排序，那么支配数应该出现在 array[len(array)/2] 上（没细做推论），这样算法复杂度会降低不少。

LZ的代码看起来确实比较简洁，但 for 里面在来一个 while True，实际上算法复杂度并不低。

作者: tubocurarine 发布时间: 2011-04-11

两道比较复杂的轩辕互动面试题(Python实现)

热门阅读

热门下载