Как я могу найти и напечатать наименьшее число в массиве, которое встречается ровно K раз в массиве, где K - ввод пользователя? - PullRequest
Новая
       55

Как я могу найти и напечатать наименьшее число в массиве, которое встречается ровно K раз в массиве, где K - ввод пользователя?

0 голосов
/ 21 апреля 2020

Ранее я использовал вложенный подход, который дает мне TLE. Мы не можем использовать вложенный подход для этого. - ограничение по времени составляет 1 сек c и 5000 КБ памяти. Вот мой вложенный подход 

for (int i = 0; i < n; i++) {
    if (arr[i] > 0) {
        int count = 1;
        for (int j = i + 1; j < n; j++)
            if (arr[i] == arr[j])
                count += 1;
        if (count == k)
            res = Math.min(res, arr[i]);
    }
}

Ответы [ 3 ]

0 голосов
/ 24 апреля 2020

Во-первых, вы должны получить элемент max и создать массив count длиной + 1 элемент, т. Е. Сколько времени встречаются каждый элемент, например: - arr = [2,5,1,2,3,6,3] и k = 2. Теперь посчитайте каждый элемент, n - это длина массива, c - это элемент подсчета массива 

int c[]=new int[max+1];
    for(int i=0;i<=max; i++)
    {
        c[a[i]]+=1;
    }
     Arrays.sort(a);
    //1 2 2 3 3 5 6
    for(int i=0;i<n;i++)
    {
        if(c[a[i]]==k)
        {
            System.out.print(a[i]);
            break;
        }
    }

Это даст вам желаемый результат с временной сложностью O (nLogn)

0 голосов
/ 24 апреля 2020

Как насчет простой сортировки массива и последующего обхода его для возврата первого значения, которое встречается k раз? 

// return the smallest value that occurs k times, or null if none found
static Integer smallestK(int[] a, int k)
{
    Arrays.sort(a);

    for(int i=1, j=0; i<=a.length; i++)
    {
        if(i == a.length || a[i] != a[j])
        {
            if(i - j == k) 
                return a[j];
            j = i;
        }
    }
    return null;
}

Тест: 

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

System.out.println(Arrays.toString(a));
for(int k=1; k<=4; k++)
{
    Integer val = smallestK(a.clone(), k);          
    if(val != null)
        System.out.format("k:%d, Result: %d%n", k, val);
    else
        System.out.format("k:%d, Not Found", k);
}

Вывод: 

[6, 5, 3, 1, 4, 2, 5, 2, 2]
k:1, Result: 1
k:2, Result: 5
k:3, Result: 2
k:4, Not Found
0 голосов
/ 21 апреля 2020

Вы можете попробовать использовать словарь, который отслеживает числа в качестве ключей и количество раз, которое оно появляется в качестве значения. Таким образом, вам придется только один раз go пройти через массив.

Затем в конце вы проверите, какие ключи имеют значение K, и выберите самый маленький из них.

...