137. Single Number II

Условие задачи

Дан непустой массив целых чисел. Все числа повторяются три раза, кроме одного числа. Необходимо найти это числ

Замечание: Алгоритм должен быть линейной сложности ( O(1) ). Возможно ли это сделать без дополнительной памяти?

пример

1
2

Input: [2,2,3,2]
Output: 3

1
2

Input: [0,1,0,1,0,1,99]
Output: 99

Решение

Отсортировать массив =)

Отсортировать массив входной массив. А затем пойти по массиву через два числа. И на каждом этапе сравнивать текущий со следующим. Если они не равны - то текущий является искомым уникальным числом.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func singleNumber(nums []int) int {
    sort.Ints(nums)
    
    for idx:=0; idx<len(nums); idx+=3 {
        if idx<len(nums)-3 && nums[idx]!=nums[idx+2] {
            return nums[idx]
        }
    }
    
    return nums[len(nums)-1]
}