daily pastebin goal
62%
SHARE
TWEET

Untitled

a guest May 16th, 2018 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package orderStatistic;
  2.  
  3. public class OrderStatisticsSelectionImpl<T extends Comparable<T>> implements OrderStatistics<T> {
  4.  
  5.     /**
  6.      * Esta eh uma implementacao do calculo da estatistica de ordem seguindo a
  7.      * estrategia de usar o selection sem modificar o array original. Note que seu
  8.      * algoritmo vai apenas aplicar sucessivas vezes o selection ate encontrar a
  9.      * estatistica de ordem desejada sem modificar o array original.
  10.      *
  11.      * Restricoes: - Preservar o array original, ou seja, nenhuma modificacao pode
  12.      * ser feita no array original - Nenhum array auxiliar deve ser criado e
  13.      * utilizado. - Voce nao pode encontrar a k-esima estatistica de ordem por
  14.      * contagem de elementos maiores/menores, mas sim poraplciar sucessivas
  15.      * selecoes. - Caso a estatistica de ordem nao exista no array, o algoritmo deve
  16.      * retornar null. - Considerar que k varia de 1 a N - Sugestao: o uso de
  17.      * recursao ajudara sua codificacao.
  18.      */
  19.     @Override
  20.     public T getOrderStatistics(T[] array, int k) {
  21.  
  22.         boolean valid = inputValidation(array);
  23.  
  24.         if (valid) {
  25.  
  26.             int maximoValue = 0;
  27.             int minimoValue = 0;
  28.             for (int i = 0; i < array.length; i++) {
  29.                 if (array[i].compareTo(array[maximoValue]) > 0)
  30.                     maximoValue = i;
  31.                 if (array[i].compareTo(array[minimoValue]) < 0)
  32.                     minimoValue = i;
  33.             }
  34.  
  35.             return getOrderStatisticsRec(array, k, 1, minimoValue, maximoValue);
  36.         }
  37.  
  38.         return null;
  39.     }
  40.  
  41.     private T getOrderStatisticsRec(T[] array, int k, int qtdMinimo, int lastMinimo, int maxIndex) {
  42.  
  43.         if (qtdMinimo == k)
  44.             return array[lastMinimo];
  45.  
  46.         if (qtdMinimo == array.length)
  47.             return null;
  48.        
  49.         int minimo = maxIndex;
  50.            
  51.         for (int i = 0; i < array.length; i++) {
  52.            
  53.             if (array[i].compareTo(array[minimo]) < 0) {
  54.                 if (array[i].compareTo(array[lastMinimo]) > 0)
  55.                     minimo = i;
  56.             }
  57.         }
  58.        
  59.         return getOrderStatisticsRec(array, k, qtdMinimo + 1, minimo, maxIndex);
  60.  
  61.     }
  62.  
  63.     private boolean inputValidation(T[] array) {
  64.  
  65.         if (array == null)
  66.             return false;
  67.         if (array.length == 0)
  68.             return false;
  69.  
  70.         return true;
  71.     }
  72.  
  73. }
RAW Paste Data
Top