from functools import reduce
class Solution:
    def getNum1(self,arr):#累加求和
        real_list = [i for i in range(1,len(arr)+2)]
        real_sum = reduce(lambda x,y:x+y,real_list)
        estimate_sum = sum(arr)
        return real_sum-estimate_sum

    def getNum2(self,arr):
        real_list = [i for i in range (1, len (arr) + 2)]
        real_ = reduce(lambda x,y:x^y,real_list)

        estimate_ = reduce(lambda x,y:x^y,arr)
        return real_^estimate_

S = Solution()
res = S.getNum2(arr=[1,4,3,2,7,5])
print(res)

def getMin1(arr,low,high):
    if high < low:
        return arr[0]
    if high == low:#只剩下一个元素一定是最小值
        return arr[low]
    mid = (low+high) // 2
    if arr[mid] < arr[mid-1]:#45123，1一定是最小值【奇数】
        return arr[mid]
    elif arr[mid+1] < arr[mid]: #456123,1一定是最小值【偶数】
        return arr[mid+1]
    elif arr[mid] > arr[high]:#最小值在右侧
        low = mid + 1
        return getMin1(arr,low,high)
    elif arr[mid] < arr[high]:#最小值在左侧
        high = mid
        return getMin1(arr,low,high)
    else:#这种情况无法确定最小值所在的位置，需要左右两部分分别查找
        return min(getMin1(arr,low,mid-1),getMin1(arr,mid+1,high))

def getMin(arr):
    if not arr:
        return
    else:
        return getMin1(arr,0,len(arr)-1)

#方法一：空间复杂度O(N)
def rotateArr(arr,div):
    '''
    :param arr:
    :param div:分为两个数组的切割点
    :return:
    '''
    arr1 = arr[:div+1]
    arr2 = arr[div+1:]

    return arr2+arr1

#方法二：时间复杂度O(N),空间复杂度O(1)
def rotateArr1(arr,div):
    def swap(arr,low,high):
        while low < high:
            arr[low],arr[high] = arr[high],arr[low]
            low += 1
            high -= 1

    if not arr or div < 0 or div >= len(arr):
        return
    # if div == 0 or div == len(arr) - 1:
    #     return
    swap(arr,0,div)#交换第一个子数组
    print(arr)
    swap(arr,div+1,len(arr)-1)#交换第二个子数组
    print(arr)
    swap(arr,0,len(arr)-1)#交换整个数组
    print(arr)
    return arr

class MaxMin:
    def __init__(self):
        self.max = None
        self.min = None

    def getMax(self):
        return self.max

    def getMin(self):
        return self.min

    def GetMaxandMin(self,arr):
        if arr == None:
            print('参数不合法')
            return
        i = 0
        lens = len(arr)
        self.max = arr[0]
        self.min = arr[0]

        #两两分组，把较小的数放到左半部分，较大的数放到右半部分
        while i < lens-1:
            if arr[i] > arr[i+1]:
                arr[i],arr[i+1] = arr[i+1],arr[i]
            i += 2
        print(arr)

        #比较每组的左半部分，找最小值
        self.min = arr[0]
        i = 2
        while i < lens:
            if arr[i] < self.min:
                self.min = arr[i]
            i += 2

        #比较每组的右半部分，找最大值
        self.max = arr[1]
        i = 3
        while i < lens:
            if arr[i] > self.max:
                self.max = arr[i]
            i += 2

        #如果数组中元素个数是奇数个，最后一个元素被分为一组，需要特殊处理
        if lens % 2 == 1:
            if self.max < arr[lens-1]:
                self.max = arr[lens-1]
            if self.min > arr[lens-1]:
                self.min = arr[lens-1]

        print(self.max)
        print(self.min)

class MaxMin_recur:
    def __init__(self):
        self.max = None
        self.min = None

    def getMax(self):
        return self.max

    def getMin(self):
        return self.min

    def GetMaxandMin(self,arr,l,r):
        if arr == None:
            return

        mid = (l + r) // 2
        list = []

        #如果只有一个元素
        if l == r:
            list.append(arr[l])
            list.append(arr[l])
            return list

        #如果有两个元素
        if l + 1 == r:
            if arr[l] >= arr[r]:
                max_ = arr[l]
                min_ = arr[r]
            else:
                max_ = arr[r]
                min_ = arr[l]
            list.append(min_)
            list.append(max_)
            return list

        L_list = self.GetMaxandMin(arr,l,mid)
        R_list = self.GetMaxandMin(arr,mid+1,r)

        #总的最大值
        max_ = L_list[1] if (L_list[1] > R_list[1]) else R_list[1]
        min_ = L_list[0] if (L_list[0] < R_list[0]) else R_list[0]

        list.append(min_)
        list.append(max_)

        return list

if __name__ == '__main__':
    maxmin = MaxMin_recur()
    arr = [1,3,6,5,14]
    l = 0
    r = len(arr) - 1
    result = maxmin.GetMaxandMin(arr,l,r)
    print(result)

class Solution:
    def getNum_1(self,arr):
        arr_dict = {}
        for num in arr:
            if num not in arr_dict:#出现一次
                arr_dict[num] = 1
            else:#出现两次
                arr_dict[num] = 0
        res = [k for k,v in arr_dict.items() if v == 1]#出现一次的元素value必定为1
        return res