- 论坛徽章:
- 0
|
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的平均数。 |
|