leetcode 摆动排序 II python 之不需要排序

排序的话，就没意思了。
不排序的话，有一个思想，就是如果奇数位置，则需要比后面一个数小，偶数位置要比后面一个数大，否则的话就和后一个数做交换。
论证了一下，在数据不重复的情况下是可以的，也很巧妙。
但此题就是要处理数字相等的情况。
如果输入是四个数，其中两个A>B，两外有另个相等的C，
则输出为sort（B,C）拼接sort（A,C）
根据这个推论，然后处理各种情况，终于搞出来了。

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def count_equal(nums):
            for i in range(len(nums)-1):
                if nums[i]==nums[i+1]:
                    return i
        
        def fourwith2equal(b,s,e):
            bigger_cp=[b,e] if b<e else [e,b]
            smaller_cp=[s,e] if s<e else [e,s]
            return bigger_cp+smaller_cp
        
        def dealwithequals(nums):
            for j in range(0,len(nums),2):
                if nums[j] != nums[i] and nums[j+1]!= nums[i] and (j==0 or j+1==len(nums)-1 or nums[j-1]!=nums[j+2]):
                    break
            head4=fourwith2equal(nums[j+1],nums[j],nums[i])
            rest=nums[:j]+nums[j+2:-2]
            if len(rest)==0:
                nums[:]=head4
            else:
                if rest[0]!=head4[-1]:
                    nums[:]=head4+rest
                    return
                is_update=False
                for j in range(1,len(rest)-1,2):
                    if rest[j]!=head4[0] and rest[j+1]!=head4[-1]:
                        is_update=True
                        nums[:]=rest[0:j+1]+head4+rest[j+1:]
                        break
                if not is_update:
                    nums[:]=rest+head4
        
        if len(nums)<=1:
            return nums
        for i in range(len(nums)-1):
            if nums[i+1]==nums[i]:
                j=i+1
                while(j<len(nums)):
                    if nums[j]==nums[i]:
                        j+=1
                        continue
                    t=nums[i+1]
                    nums[i+1]=nums[j]
                    nums[j]=t
                    break
            if i%2==0:
                if nums[i]<nums[i+1]:
                    continue
                t=nums[i]
                nums[i]=nums[i+1]
                nums[i+1]=t
                continue
            if nums[i]>nums[i+1]:
                continue
            t=nums[i]
            nums[i]=nums[i+1]
            nums[i+1]=t
        if nums[-1]!=nums[-2]:
            return
        while nums[-1]==nums[-2]:
            dealwithequals(nums)