Как найти количество различных элементов в массиве

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

46

#include <stdio.h>

// Функция для определения количества различных элементов в каждом подмассиве

// размером `k` в массиве

void findDistinctCount(int arr[], int n, int k)

{

    // рассматриваем каждый подмассив размера `k`

    for (int x = 0; x <= n — k; x++)

    {

        // поддерживает счетчик различных элементов в текущем подмассиве

        int distinct = 0;

        // текущий подмассив формируется подмассивом `arr[x, x+k)`

        for (int i = x; i < x + k; i++)

        {

            // увеличить количество различных элементов для `arr[i]` в текущем подмассиве

            distinct++;

            // проверяем, присутствует ли `arr[i]` в подмассиве `arr[x, i-1]` или нет

            for (int j = x; j < i; j++)

            {

                // если в текущем подмассиве найден повторяющийся элемент

                if (arr[i] == arr[j])

                {

                    // снимите пометку с элемента `arr[i]` как отдельный – уменьшите количество

                    distinct—;

                    break;

                }

            }

        }

        printf(«The count of distinct elements in subarray [%d, %d] «

                «is %dn», x, x + k — 1, distinct);

    }

}

int main(void)

{

    int arr[] = { 2, 1, 2, 3, 2, 1, 4, 5 };

    int k = 5;

    int n = sizeof(arr) / sizeof(arr[0]);

    findDistinctCount(arr, n, k);

    return 0;

}

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

class Main

{

    // Функция для определения количества различных элементов в каждом подмассиве

    // размера `k` в массиве

    public static void findDistinctCount(int[] arr, int k)

    {

        // рассматриваем каждый подмассив размера `k`

        for (int x = 0; x <= arr.length — k; x++)

        {

            // поддерживает счетчик различных элементов в текущем подмассиве

            int distinct = 0;

            // текущий подмассив формируется подмассивом `arr[x, x+k)`

            for (int i = x; i < x + k; i++)

            {

                // увеличить количество различных элементов для `arr[i]` в текущем подмассиве

                distinct++;

                // проверяем, присутствует ли `arr[i]` в подмассиве `arr[x, i-1]` или нет

                for (int j = x; j < i; j++)

                {

                    // если в текущем подмассиве найден повторяющийся элемент

                    if (arr[i] == arr[j])

                    {

                        // снимите пометку с элемента `arr[i]` как отдельный – уменьшите количество

                        distinct—;

                        break;

                    }

                }

            }

            System.out.printf(«The count of distinct elements in subarray [%d, %d]»

                                + » is %dn», x, x + k — 1, distinct);

        }

    }

    public static void main(String[] args)

    {

        int[] arr = { 2, 1, 2, 3, 2, 1, 4, 5 };

        int k = 5;

        findDistinctCount(arr, k);

    }

}

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

# Функция для определения количества различных элементов в каждом подсписке

# размера `k` в списке

def findDistinctCount(A, k):

    # рассматривает каждый подсписок размера `k`

    for x in range(len(A) — k + 1):

        # поддерживает счетчик отдельных элементов в текущем подсписке.

        distinct = 0

        # текущий подсписок формируется из подсписка `A[x, x+k)`

        for i in range(x, x + k):

            # увеличить количество различных для `A[i]` в текущем подсписке

            distinct = distinct + 1

            # проверяет, присутствует ли `A[i]` в подсписке `A[x, i-1]` или нет

            for j in range(x, i):

                # Если в текущем подсписке найден повторяющийся элемент

                if A[i] == A[j]:

                    # снять пометку с элемента `A[i]` как отдельный – уменьшить количество

                    distinct = distinct — 1

                    break

        print(«The count of distinct elements in sublist»,

            f«[{x}, {x + k — 1}] is {distinct}»)

if __name__ == ‘__main__’:

    A = [2, 1, 2, 3, 2, 1, 4, 5]

    k = 5

    findDistinctCount(A, k)

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

#include <iostream>

#include <vector>

#include <unordered_set>

using namespace std;

// Функция для поиска всех различных элементов, присутствующих в каждом подмассиве

// размером `k` в массиве

void findDistinctCount(vector<int> const &input, int k)

{

    // цикл по вектору

    for (int i = 0; i < input.size() — (k — 1); i++)

    {

        unordered_set<int> distinct(input.begin() + i, input.begin() + i + k);

        cout << «The count of distinct elements in subarray [« << i << «, «

             << (i + k — 1) << «] is « << distinct.size() << endl;

    }

}

int main()

{

    vector<int> input = { 2, 1, 2, 3, 2, 1, 4, 5 };

    int k = 5;

    findDistinctCount(input, k);

    return 0;

}

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

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

class Main

{

    // Функция для поиска всех различных элементов, присутствующих в каждом подмассиве

    // размера `k` в массиве

    public static void findDistinctCount(List<Integer> input, int k)

    {

        // цикл по списку

        for (int i = 0; i < input.size() — (k — 1); i++)

        {

            Set<Integer> distinct = new HashSet<>();

            distinct.addAll(input.subList(i, i + k));

            System.out.println(«The count of distinct elements in «

                + «subarray [« + i + «, « + (i + k — 1) + «] is «

                + distinct.size());

        }

    }

    public static void main(String[] args)

    {

        List<Integer> input = Arrays.asList( 2, 1, 2, 3, 2, 1, 4, 5 );

        int k = 5;

        findDistinctCount(input, k);

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Функция для поиска всех отдельных элементов, присутствующих в каждом подсписке.

# размера `k` в списке

def findDistinctCount(A, k):

    # цикл по списку

    for i in range(len(A) — (k — 1)):

        distinct = set(A[i:i+k])

        print(f«The count of distinct elements in sublist [{i}, {(i + k — 1)}] is»,

            len(distinct))

if __name__ == ‘__main__’:

    input = [2, 1, 2, 3, 2, 1, 4, 5]

    k = 5

    findDistinctCount(input, k)

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

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

#include <iostream>

#include <vector>

#include <unordered_map>

#include <unordered_set>

using namespace std;

// Функция для определения количества различных элементов в каждом подмассиве

// размером `k` в массиве

void findDistinctCount(vector<int> const &input, int k)

{

    // карта для хранения частоты элементов в текущем окне размером `k`

    unordered_map<int, int> freq;

    // поддерживает количество различных элементов в каждом подмассиве размера `k`

    int distinct = 0;

    // цикл по массиву

    for (int i = 0; i < input.size(); i++)

    {

        // игнорируем первые `k` элементов

        if (i >= k)

        {

            // удалить первый элемент из подмассива, уменьшив его

            // частота на карте

            freq[input[i — k]]—;

            // уменьшаем количество различных, если осталось 0

            if (freq[input[i — k]] == 0) {

                distinct—;

            }

        }

        // добавляем текущий элемент в подмассив, увеличивая его

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

        freq[input[i]]++;

        // увеличиваем счетчик уникальных элементов на 1, если элемент встречается первым

        // время в текущем окне

        if (freq[input[i]] == 1) {

            distinct++;

        }

        // вывести количество различных элементов в текущем подмассиве

        if (i >= k — 1)

        {

            cout << «The count of distinct elements in subarray [« <<

                (i — k + 1) << «, « << i << «]» << » is « << distinct << endl;

        }

    }

}

int main()

{

    vector<int> input = { 1, 1, 2, 1, 3 };

    int k = 3;

    findDistinctCount(input, k);

    return 0;

}

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

46

47

48

49

50

51

52

53

54

55

56

57

58

import java.util.HashMap;

import java.util.Map;

class Main

{

    // Функция для определения количества различных элементов в каждом подмассиве

    // размера `k` в массиве

    public static void findDistinctCount(int[] A, int k)

    {

        // карта для хранения частоты элементов в текущем окне размером `k`

        Map<Integer, Integer> freq = new HashMap<>();

        // поддерживает количество различных элементов в каждом подмассиве размера `k`

        int distinct = 0;

        // цикл по массиву

        for (int i = 0; i < A.length; i++)

        {

            // игнорируем первые `k` элементов

            if (i >= k)

            {

                // удалить первый элемент из подмассива, уменьшив его

                // частота на карте

                freq.put(A[i — k], freq.getOrDefault(A[i — k], 0) — 1);

                // уменьшаем количество различных, если осталось 0

                if (freq.get(A[i — k]) == 0) {

                    distinct—;

                }

            }

            // добавляем текущий элемент в подмассив, увеличивая его

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

            freq.put(A[i], freq.getOrDefault(A[i], 0) + 1);

            // увеличиваем счетчик уникальных элементов на 1, если элемент встречается первым

            // время в текущем окне

            if (freq.get(A[i]) == 1) {

                distinct++;

            }

            // вывести количество различных элементов в текущем подмассиве

            if (i >= k — 1)

            {

                System.out.println(«The count of distinct elements in subarray [« +

                        (i — k + 1) + «, « + i + «]» + » is « + distinct);

            }

        }

    }

    public static void main(String[] args)

    {

        int[] input = { 1, 1, 2, 1, 3 };

        int k = 3;

        findDistinctCount(input, k);

    }

}

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

# Функция для определения количества различных элементов в каждом подсписке

# размера `k` в списке

def findDistinctCount(A, k):

    # Словарь # для хранения частоты элементов в текущем окне размером `k`

    freq = {}

    # поддерживает количество отдельных элементов в каждом подсписке размера `k`.

    distinct = 0

    # цикл по списку

    for i in range(len(A)):

        # игнорирует первые `k` элементов

        if i >= k:

            # удалить первый элемент из подсписка, уменьшив его

            # Частота # в словаре

            freq[A[i — k]] -= 1

            # уменьшает количество различных, если у нас осталось 0

            if freq.get(A[i — k]) == 0:

                distinct = distinct — 1

        # добавить текущий элемент в подсписок, увеличив его

        # Количество # в словаре

        freq[A[i]] = freq.get(A[i], 0) + 1

        # увеличивает количество уникальных элементов на 1, если элемент встречается в первый раз.

        # время в текущем окне

        if freq.get(A[i]) == 1:

            distinct = distinct + 1

        # вывести количество различных элементов в текущем подсписке

        if i >= k — 1:

            print(«The count of distinct elements in sublist»,

                f«[{(i — k + 1)}, {i}] is {distinct}»)

if __name__ == ‘__main__’:

    input = [1, 1, 2, 1, 3]

    k = 3

    findDistinctCount(input, k)