10003. Counting Elements

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

2020.04.07 497 слов Пару мгновений

Содержание

Решение задачи 10003 “Counting Elements” с LeetCode.

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

Given an integer array arr, count element x such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Constraints:

1 <= arr.length <= 1000
0 <= arr[i] <= 1000

Данн массив целых чисел arr. подсчитать количество таких элементов x, для которых в массиве существуют элементы x+1. Если такой элемент x встречается несколько раз - считать каждый отельно.

ограничения

1 <= arr.length <= 1000
0 <= arr[i] <= 1000

пример

1
2
3


Input: arr = [1,2,3]
Output: 2
Объяснение:1 и 2 учтены, поскольку для них существют 2 и 3 соотвественно.

1
2
3


Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Объяснение: Ни одно число не учтено, посколько в массиве нет 2,4,6 и 8.

1
2
3


Input: arr = [1,3,2,3,5,0]
Output: 3
Объяснение:0, 1 и 2 учтены, поскольку 1, 2 и 3 есть в массиве.

1
2
3


Input: arr = [1,1,2,2]
Output: 2
Объяснение: две идиницы учтены, потому что есть 2.

Решение

Использовать коллекцию

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

Создать коллекцию, где ключом будет число, а значение - кол-во раз вхождения числа в исходный массив.

Идем по исходному массиву и пересчитываем все числа.

Идем по коллекции, берем текущее число. Если в коллекции есть значения для текущего числа + 1 - то плюсуем к результату кол-во исходных чисел.

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


func countElements(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    
    res := 0
    
    up := make(map[int]int,0)
    for idx := range arr {
        up[arr[idx]]++
    }
    
    for jdx:= range up {
        if _, ok := up[jdx+1]; ok {
            res+=up[jdx]
        }
    }
    
    return res
}

Сортировка с пересчетом

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

Отсортировать исходный массив

Идти по элементам, считать кол-во текущих элементов ( то есть сколько раз повторяется число ).

Как только встретили новое число

если оно больше более чем на 1 - сбросить счетчики и считать заново
если оно больше ровно на 1 - добавить к итоговому результату кол-во текущих элементов и обнулить их счетчик.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


func countElements(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    sort(arr)
    res := 0
    cur :=0
    curv:=arr[0]
    prev := 0
    
    for idx := range arr {
        if arr[idx]>curv && arr[idx]-curv > 1 {
            prev = 0
            cur = 0
            curv = arr[idx]
            
        }
        if arr[idx]>curv && arr[idx]-curv == 1 {
            prev = cur
            cur = 0
            curv = arr[idx]
        }
        if arr[idx] == curv {
            cur++
            if prev>0 {
                res+=prev
                prev = 0
            }
        }
    }
    
    return res
}

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