codewars（python）練習(xí)筆記十九：求數(shù)組的質(zhì)因數(shù)的倍數(shù)和集
題目
Given an array of positive or negative integers
I= [i1,..,in]
you have to produce a sorted array P of the form
[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]
P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java, C#, C, C++ and as an array of arrays in other languages.
Example:
I = [12, 15] # result = [[2, 12], [3, 27], [5, 15]]
[2, 3, 5] is the list of all prime factors of the elements of I, hence the result.
Notes:
? It can happen that a sum is 0 if some numbers are negative!
Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.
? In Fortran - as in any other language - the returned string is not permitted to contain any redundant trailing whitespace: you can use dynamically allocated character strings.
Sample Tests:
a = [12, 15]
test.assert_equals(sum_for_list(a), [[2, 12], [3, 27], [5, 15]])
list: [12, 15]
result: [[2, 12], [3, 27], [5, 15]]
list: [15, 21, 24, 30, 45]
result: [[2, 54], [3, 135], [5, 90], [7, 21]]
list: [15, 21, 24, 30, -45]
result: [[2, 54], [3, 45], [5, 0], [7, 21]]
list: [107, 158, 204, 100, 118, 123, 126, 110, 116, 100]
result: [[2, 1032], [3, 453], [5, 310], [7, 126], [11, 110], [17, 204], [29, 116], [41, 123], [59, 118], [79, 158], [107, 107]]
list: [-29804, -4209, -28265, -72769, -31744]
result: [[2, -61548], [3, -4209], [5, -28265], [23, -4209], [31, -31744], [53, -72769], [61, -4209], [1373, -72769], [5653, -28265], [7451, -29804]]
題目大意
對(duì)一個(gè)數(shù)組，如[12,15],首先對(duì)每個(gè)元素進(jìn)行質(zhì)因數(shù)分解，比如，12 = 2X2X3，則12有質(zhì)因數(shù) 2，3；15 =3X5，有質(zhì)因數(shù)3，5。
則數(shù)組有不同質(zhì)因數(shù)2，3，5。
那么，按從小到大的順序：2的倍數(shù)有12；3的倍數(shù)有：12、15；5的倍數(shù)有：15。
則可以輸出[(2,12),(3,12+15),(5,15)] =>簡(jiǎn)化[(2,12),(3,27),(5,15)].
注意，負(fù)整數(shù)的質(zhì)因數(shù)和對(duì)應(yīng)的正整數(shù)的質(zhì)因數(shù)相同。
我的解法：
import math
def isprime(n):
if n <= 1: return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0: return False
return True
def sum_for_list(lst):
arrArr = []
for num in lst:
if num < 0: num=-num
arrArr += [item for item in range(1,num+1) if(num%item == 0 and isprime(item) and item not in arrArr)]
temp_arr = []
for item in sorted(arrArr):
temp = 0
for num in lst:
if num%item == 0:
temp += num
temp_arr.append([item,temp])
return temp_arr
然后想了想，是不是能簡(jiǎn)化一下提升一下效率，就考慮到是不是利用數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)化一下加和那一步的效率。
#!/usr/bin/python
import math
def isprime(n):
if n <= 1: return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0: return False
return True
def sum_for_list(lst):
keyarr = []
kvarr = []
for num in lst:
if num < 0:num=-num
for item in range(1,num+1):
if num%item == 0 and isprime(item):
kvarr.append({item:num})
if item not in keyarr:keyarr.append(item)
res = []
for key in keyarr:
vsum = 0
for dic in kvarr:
if dic.keys()[0] == key:
vsum += dic[key]
res.append([key,vsum])
return res
利用數(shù)組嵌套，不如直接利用dict，所以繼續(xù)優(yōu)化如下：
#!/usr/bin/python
import math
def isprime(n):
if n <= 1: return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0: return False
return True
def sum_for_list(lst):
kvdict = {}
for num in lst:
if num < 0:num=-num
for item in range(1,num+1):
if num%item == 0 and isprime(item):
if item in kvdict.keys():
kvdict[item].append(num)
else:
kvdict[item] = [num]
res = []
for key in kvdict.keys():
vsum = 0
for num in kvdict[key]:
vsum += num
res.append([key,vsum])
return res
繼續(xù)優(yōu)化：
#!/usr/bin/python
import math
def isprime(n):
if n <= 1: return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0: return False
return True
def sum_for_list(lst):
kvdict = {}
for num in lst:
if num < 0:num=-num
for item in range(1,num+1):
if num%item == 0 and isprime(item):
if kvdict.has_key(item):
kvdict[item].append(num)
else:
kvdict[item] = [num]
res = [[key,sum(kvdict[key])] for key in sorted(kvdict.keys())]
return res
然后再在上面的嵌套想辦法，首先是if else。abs(num)可以直接取num的絕對(duì)值。三目運(yùn)算也可以減少代碼行數(shù)：
#!/usr/bin/python
import math
def isprime(n):
if n <= 1: return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0: return False
return True
def sum_for_list(lst):
kvdict = {}
for num in lst:
for item in range(1,abs(num)+1):
if abs(num)%item == 0 and isprime(item):
kvdict[item] = kvdict[item]+[num] if kvdict.has_key(item) else [num]
res = [[key,sum(kvdict[key])] for key in sorted(kvdict.keys())]
return res
將判斷質(zhì)數(shù)的方法優(yōu)化：
#!/usr/bin/python
import math
def isprime(n):
return n in filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i==0], range(2,n+1))
def sum_for_list(lst):
kvdict = {}
for num in lst:
for item in range(1,abs(num)+1):
if abs(num)%item == 0 and isprime(item):
kvdict[item] = kvdict[item]+[num] if kvdict.has_key(item) else [num]
res = [[key,sum(kvdict[key])] for key in sorted(kvdict.keys())]
return res
另一種思路：
先求出需要求的數(shù)組的最大值以內(nèi)的質(zhì)數(shù)的集。然后再找出對(duì)應(yīng)的質(zhì)數(shù)的集合。這個(gè)思路是以空間換取部分時(shí)間，在給定數(shù)組的最大值較小的時(shí)候，比較合適。但，如果給定數(shù)組的最大值比較大，那么要生成的質(zhì)數(shù)集就會(huì)非常大，生成效率也會(huì)大幅降低。
#!/usr/bin/python
import math
def func_get_prime(n):
return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i==0], range(2,n+1))
def sum_for_list(lst):
temp_lst = [abs(item) for item in lst]
prime_arr = func_get_prime(sorted(temp_lst)[len(temp_lst)-1])
kvdict = {}
for num in temp_lst:
for key in prime_arr:
if key < num and num%key == 0:
kvdict[key] = kvdict[key]+[num] if kvdict.has_key(key) else [num]
elif key > num:
break
res = [[key,sum(kvdict[key])] for key in sorted(kvdict.keys())]
return res
牛逼人是怎么寫的
我想了好久，都沒有特別好優(yōu)化算法，然后提交之后，一個(gè)牛逼的算法轟然而至：
def sum_for_list(lst):
factors = {i for k in lst for i in xrange(2, abs(k)+1) if not k % i}
prime_factors = {i for i in factors if not [j for j in factors-{i} if not i % j]}
return [[p, sum(e for e in lst if not e % p)] for p in sorted(prime_factors)]
這個(gè)是就對(duì)python語法的仔細(xì)掌握了，但從效率上和時(shí)間復(fù)雜度上來講，也就這樣了。
總結(jié)：
畢竟，輸入數(shù)組的情況，千變?nèi)f化，既可以是[12,13,14]這樣的，也可能是[90000,90001,90002]這樣的，還有可能是[12,14,9000001]這樣的，只能通過大量測(cè)試，找出在各種情況下都均衡的算法，而沒有說是在任何一種情況下的最優(yōu)解法。
