有序数组中出现一次的元素

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param v int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4c67fc80c37649ac906fee76ec82beb4?tpId=196&tqId=40508&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        left, right = 0, len(v) - 1
        当left < right时，二分查找res:
            mid = left + (right - left) / 2
            如果v[mid] != v[left] and v[mid] != v[right]：
                return v[mid]
            否则，如果v[mid] == v[mid - 1]：
                    若(mid + 1) % 2 == 0: # 解在区间[mid + 1, right]
                        left = mid + 1
                    否则：
                        right = mid - 2
            否则： #  v[mid] == v[mid + 1]
                若mid % 2 == 0：# 解在区间[mid + 2, right]
                    left = mid + 2
                否则：
                    right = mid - 1
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def singleElement(self, v):
        # write code here
        left, right = 0, len(v) - 1

        while left < right:
            mid = left + (right - left) / 2
            if v[mid] != v[mid - 1] and v[mid] != v[mid + 1]:
                return v[mid]
            elif v[mid] == v[mid - 1]:
                if (mid + 1) % 2 == 0:  # 解在区间[mid + 1, right]
                    left = mid + 1
                else:
                    right = mid - 2
            else:  # v[mid] == v[mid + 1]
                if mid % 2 == 0:  # 解在区间[mid + 2, right]
                    left = mid + 2
                else:
                    right = mid - 1

        return v[left]


if __name__ == "__main__":
    sol = Solution()

    # nums = [1, 2, 2, 3, 3]

    # nums = [1, 1, 5, 5, 8, 8, 9, 10, 10]

    nums = [5, 5, 6, 6, 9, 10, 10, 11, 11, 13, 13, 14, 14]

    res = sol.singleElement(nums)

    print res

class Solution {
public:
    int singleElement(vector<int>& v) {
     
        int i=0,j=v.size()-1;
        while(i<j){
            int mid=(j-i)/2+i;
            if(v[mid]==v[mid^1]){
                i=mid+1;
            }else{
                j=mid;
            }
        }
        return v[i];
    }
};

public int singleElement (ArrayList<Integer> v) {
        // write code here
        int res=0;
        for(int a : v){
            res=res^a;
        }
        return res;
    }

from collections import Counter
class Solution:
    def singleElement(self , v: List[int]) -> int:
        # write code here        
        return sorted(Counter(v).items(), key = lambda x:x[1])[0][0]