记录一下笔试碰到的一个问题
和导师一起讨论了下，用优先队列可以解决。
在Python中用dict维护。
为了保证一定是交叉放入的，在res中插入一个新的数后，该数对暂时不放入原数组中，暂时用prev存放。
def rearrangeArray(arr):
lenArray=len(arr)
dict={}
for i in range(lenArray):
if arr[i] in dict:
dict[arr[i]]+=1
else:
dict[arr[i]]=1
tmp=[]
used=[]
for i in range(lenArray):
if not arr[i] in used and arr[i] in dict:
tmp.append([arr[i],dict[arr[i]]])
used.append(arr[i])
res=[0]*lenArray
tmp.sort(key=lambda x:x[1],reverse=True)
prev=[]
i=0
while tmp[0][1]>0:
tmpD=tmp[0]
tmp.pop(0)
res[i]=tmpD[0]
if prev:
tmp.append(prev)
prev=[tmpD[0],tmpD[1]-1]
i+=1
tmp.sort(key=lambda x:x[1],reverse=True)
flag=0
s=""
for i in range(len(res)):
if res[i]==0:
print("No Array Match The Requirements!")
flag=1
break
s=s+str(res[i])+" "
if flag==0:
print(s)
A=[2,2,3,3,1,1,1,1]
B=[1,1,1,1,1,2,2,2]
rearrangeArray(A)
rearrangeArray(B) 有更好的方法欢迎交流！ 看了lc原题，小改了一下调整了边界情况：
class Solution:
def reorganizeString(self, s: str) -> str:
lenArray = len(s)
dict = {}
for i in range(lenArray):
if s[i] in dict:
dict[s[i]] += 1
else:
dict[s[i]] = 1
tmp = []
used = []
for i in range(lenArray):
if not s[i] in used and s[i] in dict:
tmp.append([s[i], dict[s[i]]])
used.append(s[i])
res = [0] * lenArray
tmp.sort(key=lambda x: x[1], reverse=True)
prev = []
i = 0
if tmp[0][1]>(lenArray+1)//2:
return ""
if len(tmp)<=1 and tmp[0][1]>1:
return ""
if len(tmp)<=1 and tmp[0][1]==1:
return tmp[0][0]
while tmp[0][1] > 0:
tmpD = tmp[0]
tmp.pop(0)
res[i] = tmpD[0]
if prev:
tmp.append(prev)
prev = [tmpD[0], tmpD[1] - 1]
i += 1
tmp.sort(key=lambda x: x[1], reverse=True)
flag = 0
s = ""
for i in range(len(res)):
if res[i] == 0:
# print("No Array Match The Requirements!")
flag = 1
return ""
if flag == 0:
# print(res)
return "".join(res) 
投递完美世界等公司10个岗位 >
