136. Single Number

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.04.05 308 слов Пару мгновений

Содержание

Решение задачи 136 “Single Number” с LeetCode.

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

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

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

пример

1
2


Input: [2,2,1]
Output: 1

1
2


Input: [4,1,2,1,2]
Output: 4

Решение

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

Идея алгоритма:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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


func sort (nums []int) {
    for idx := range nums {
        k := idx
        for jdx := idx-1;jdx>=0;jdx-- {
            if nums[jdx]>nums[k] {
                nums[jdx],nums[k] = nums[k], nums[jdx]
                k = jdx
            }
        }
    }
}

Подсчет элементов

Идея алгоритма:

Завести коллекцию число<->кол-во вхождений.Пройтись по исходному массиву, записывая встреченные числа в коллекцию ( инкрементировать кол-во встреченных раз) .

Пройтись по коллекции в поисках элемента, который встретился лишь единожды.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func singleNumber(nums []int) int {
    q:= make(map[int]int,0)
    
    for idx:=0;idx<len(nums);idx++ {
        if _,ok := q[nums[idx]];!ok {
            q[nums[idx]] = 0
        }
       q[nums[idx]]++
    }
    
    for idx:=range q {
        if q[idx] == 1 {
            return idx
        }
    }
    return 0
}

XOR

Идея алгоритма:

Известно, что оперция xor двух одинаковых чисел равно нулю. Посколько в нашем массиве все числа (кроме одного) встречаются ровно 2 раза – можно проксорить весь массив – получии искомое число.

1
2
3
4
5
6


func singleNumber(nums []int) int {
    for idx:=1;idx<len(nums);idx++ {
       nums[0] = nums[0] ^  nums[idx]
    }
    return nums[0]
}