记录一下笔试碰到的一个问题

和导师一起讨论了下，用优先队列可以解决。

在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)