Love, and to be Loved.

我愛你,你是自由的。

平衡點問題和支配點問題(轉)

1. 平衡點問題

平衡點:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的總和爲24,25後面的總和也是24,25這個點就是平衡點;假如一個數組中的元素,其前面的部分等於後面的部分,那麼這個點的位序就是平衡點。
要求:返回任何一個平衡點
使用sum函数累加所有的数。
使用一个变量fore来累加序列的前部。直到满足条件fore<(total-number)/2;

numbers = [1,3,5,7,8,2,4,20]  
#find total  
total=sum(numbers)  
#find num  
fore=0  
for number in numbers:  
   if fore<(total-number)/2 :  
  fore+=number  
   else:  
  break  
#print answer  
if fore == (total-number)/2 :  
   print number  
else :  
   print r'not found'  

算法簡單,而且是O(n)的。
PS 上述解題思路爲題目只考慮序列只包括正數的情況(有唯一平衡點),當序列中有負數的時候,平衡點不一定唯一。

2. 支配點問題

支配數:數組中某個元素出現的次數大於數組總數的一半時就成爲支配數,其所在位序成為支配點;比如int[] a = {3,3,1,2,3},3爲支配數,0,1,4分别爲支配點。
要求:返回任何一個支配點
《編程之美》中有答案,就是尋找水王那篇。
具體方法是:將序列排序,取中位數——注意,如果一個數出現次數大於整體的一半,那麼排序之後支配數一定在中間,然後驗證是否正確。

numbers = [1,3,4,3,3]  
#calculate  
numbers.sort()  
lens=len(numbers)  
candidate=numbers[lens/2]  
#validate  
N=0  
for number in numbers:  
if number==candidate:  
   N+=1  
#print answer  
if (N>=lens/2):  
 print numbers[lens/2]  
else :  
   print 'not found'  

Origin
Reference