3

Estou implementado um método que recebe um valor inteiro k (que representa a quantidade de "vagas") e duas listas (p e q) de Integer e efetua algumas operações.

Utilizando stream, verifico quais elementos da lista p possuem valor >= que os valores da lista q. Caso exista, preciso armazenar a posição (índice + 1) de cada item numa outra lista. Contudo esta terceira lista só pode ter uma quantidade de elementos <= o valor k passado por parâmetro.

O código implementado encontra-se abaixo, contudo preciso melhorar o desempenho dele (acredito que os 2 forEach existentes estão piorando o desempenho).

public static List<Integer> kthPerson(int k, List<Integer> p, List<Integer> q) {

        List<Integer> busList = new ArrayList<>();

        q.stream().forEach(time -> {
            List<Integer> lista = new ArrayList<>();

            IntStream.range(0, p.size()).filter(i -> (p.get(i) >= time && lista.size() < k)).forEach(i -> lista.add(i+1) );
            int size = lista.size();
            if(size < k){
               busList.add(0);
            }else{
                if (lista != null && !lista.isEmpty()) {
                    busList.add(lista.get(size - 1));
                }
            }
        });
        return busList;

    }

}
1
  • @MarcosAntônio eu vi sua questão e as respostas. Obrigado por recomendar o link. Como você fez para remover os casos repetidos? Você implementou utilizando for aninhados ou usou stream?
    – Yan
    Commented 26/05/2020 às 12:30

2 Respostas 2

3

Dada a sua descrição, acho que seu código não está certo:

verifico quais elementos da lista p possuem valor >= que os valores da lista q. Caso exista, preciso armazenar a posição (índice + 1) de cada item numa outra lista. Contudo esta terceira lista só pode ter uma quantidade de elementos <= o valor k

Testei o seu código com as listas abaixo:

List<Integer> p = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90);
List<Integer> q = Arrays.asList(10, 20, 30, 40, 50);
System.out.println(kthPerson(3, p, q));

E o resultado foi:

[3, 4, 5, 6, 7]

Só que a posição 3 (que corresponde ao índice 2) de p é o número 30, que não é maior que os valores de q (já que q possui os valores 40 e 50, que são maiores que 30). Além disso, o resultado tem 5 elementos, que é maior que k.

Enfim, não ficou muito claro o que é para fazer. Eu entendi de duas maneiras:

  1. verificar os elementos de p que são maiores que todos os elementos de q
  2. verificar os elementos de p que são maiores que o elemento de q que está na mesma posição

Veremos soluções para cada caso.


Opção 1

Se a ideia é verificar os elementos de p que são maiores que todos os elementos de q, então não precisa percorrer q várias vezes. Basta achar o maior elemento de q e verificar quais elementos de p são maiores ou iguais a ele. Depois basta pegar os primeiros k elementos e retornar a lista:

public static List<Integer> kthPersonOpcao1Stream(int k, List<Integer> p, List<Integer> q) {
    // encontrar o maior elemento de q
    int maxQ = Collections.max(q);
    return IntStream
        // iterar pelos índices de p
        .range(0, p.size())
        // pegar os elementos maiores ou iguais a maxQ
        .filter(i -> p.get(i) >= maxQ)
        // pegar somente os k primeiros
        .limit(k)
        // somar 1 ao índice
        .map(i -> i + 1)
        // converter os valores int para Integer
        .boxed()
        // coletar os valores em uma List
        .collect(Collectors.toList());
}

Mas se a preocupação é desempenho, talvez você não devesse usar streams, já que elas são mais lentas que um loop tradicional. Claro que para poucas listas pequenas não fará tanta diferença assim, mas de qualquer forma, a solução sem stream seria bem simples:

public static List<Integer> kthPersonOpcao1Loop(int k, List<Integer> p, List<Integer> q) {
    int maxQ = Collections.max(q);
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < p.size() && result.size() < k; i++) {
        if (p.get(i) >= maxQ) {
            result.add(i + 1);
        }
    }
    return result;
}

Repare na condição do for (i < p.size() && result.size() < k), que verifica se eu já comparei todos os elementos de p e se a lista de resultados tem k elementos. Assim ele já cobre também os casos em que são encontrados menos que k elementos (pois k é o tamanho máximo que a lista de resultados pode ter, mas nada garante que sempre encontrará k elementos).


Opção 2

Se a ideia é comparar cada elemento de p com o elemento de q que está na mesma posição, primeiro precisamos saber qual das listas é menor (por exemplo, se p tiver 10 elementos e q tiver 4, eu não preciso verificar os 10 elementos de p, basta verificar os 4 primeiros).

O código é bem similar à opção 1, a diferença é que em vez de comparar os elementos de p com o maior elemento de q, eu comparo apenas com os que estão na mesma posição:

// com stream
public static List<Integer> kthPersonOpcao2Stream(int k, List<Integer> p, List<Integer> q) {
    // só preciso iterar até o tamanho da menor das listas
    int size = Math.min(p.size(), q.size());
    return IntStream
        // iterar pelos índices até "size"
        .range(0, size)
        // pegar os elementos de p maiores ou iguais ao elemento de q na mesma posição
        .filter(i -> p.get(i) >= q.get(i))
        // pegar somente os k primeiros
        .limit(k)
        // somar 1 ao índice
        .map(i -> i + 1)
        // converter os valores int para Integer
        .boxed()
        // coletar os valores em uma List
        .collect(Collectors.toList());
}

// sem stream
public static List<Integer> kthPersonOpcao2Loop(int k, List<Integer> p, List<Integer> q) {
    int size = Math.min(p.size(), q.size());
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < size && result.size() < k; i++) {
        if (p.get(i) >= q.get(i)) {
            result.add(i + 1);
        }
    }
    return result;
}
2
  • Muito obrigado pela sua resposta.
    – Yan
    Commented 26/05/2020 às 12:31
  • @Yan Se a resposta resolveu o seu problema, vc pode aceitá-la, veja aqui como e porque fazê-lo. Não é obrigatório, mas é uma boa prática do site, para indicar a futuros visitantes que aquilo resolveu o problema. Não esqueça que vc também pode votar na resposta, caso tenha achado útil.
    – hkotsubo
    Commented 26/05/2020 às 12:33
1

Encontrei uma boa solução para esse problema nessa pargunta How to find all K-th elements for each expiration time, o melhor tempo obtido foi utilizando Arrays ao invés de List/Streams. Caso o problema te forneça os dados em List é só fazer um parse para Array e no final realiza outro parse de volta para List, só dessa forma consegui passar em todos os caso de teste.

public static int[] kth(int k, int[] t, int[] e) {
        int[] kth = new int[e.length];

        if (k > t.length)
            return kth;

        Arrays.sort(e);
        int c = 0;

        for (int i = 0; i < e.length; i++) {            
            for (int j = 0; j < t.length; j++) {
                if (t[j] >= e[i])
                    c++;

                if (c >= k) {
                    kth[i] = j + 1;
                    break;
                }
            }

            if (c < k)
                break;

            c = 0;
        }

        return kth;
}
2
  • @MarcosAntônio eu vi sua questão e as respostas. Obrigado por recomendar o link. Como você fez para remover os casos repetidos? Você implementou utilizando for aninhados ou usou stream?
    – Yan
    Commented 28/05/2020 às 19:05
  • @Yan eu removi os elementos repetidos usando Stream e no final criei o array List com todos os elementos Commented 28/05/2020 às 21:27

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .