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

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的平均数。

评论

6 楼 edison0951 2010-02-22  

对koth的JAVA代码的小意见，为什么不把b写全，那样一看就知道什么意思，还有FOR循环第一个参数为什么不写？（我也是学过JAVA的人），koth很不注意代码呀。

5 楼 edison0951 2010-02-22  

如果不计有唯一性，返回任意一个即可，题目也没有规定一定要返回全部的。

4 楼 koth 2010-02-22  

汗，唯一性应该是有个大前提，只能是正数。要不然可以有多个平衡点的。

3 楼 koth 2010-02-22  

补充下：平衡点的唯一性是容易证明的，所以除非没有平衡点要不就只有一个。这从一方面说明程序的正确性。

2 楼 koth 2010-02-22  

平衡点Java代码， 时间复杂度Ｏ（Ｎ）

 public int calcBalance(int arr[])
    {
        int left[]=new int[arr.length];
        int right[]=new int[arr.length];
        int b=arr.length-1;
        for(int i=0;i<left.length;i++)
        {
            if(i==0)
            {
                left[i]=0;
            }
            else
            {
                left[i]=left[i-1]+arr[i-1];
            }
        }
        for(;b>=0;b--)
        {
            if(b==arr.length-1)
            {
                right[b]=0;
            }
            else
            {
                right[b]=right[b+1]+arr[b+1];
            }
            if(left[b]==right[b])return b;
        }
        return b;
        
    }

二楼贴的平衡点还是25，可找出

1 楼 真水无香 2010-02-22  

请教一下{1,3,5,7,8,25,1,5,7,8,3}的平衡点是多少？用上面的程序能算出来吗？