2016-09-06 5 views
-3

Я написал код для вычисления ранга каждого элемента массива double [] в следующем коде. Например, если у меня есть double массив {3, 1.3, 2, 3}, тогда я считаю ранг {2, 0, 1, 2}. Она была рассчитана какНайти ранг каждого элемента массива double [] лучше в Java

  • 1,3 наименее так он получил ранг 0.
  • 2 является следующим, поэтому он получил ранг 1.
  • 3 является следующим большим числом, так как через 3 Надевать ранг- .
public static void main() { 
    double[] x = {3, 1.3, 2, 3}; 
    System.out.println(Arrays.toString(x) + " - original"); 
    System.out.println("[2, 0, 1, 2] - should be"); 
    System.out.println(Arrays.toString(findRank(x)) + " - our rank"); 
} 

private static int[] findRank(double[] x){ 
    List<Double> lst = new ArrayList<Double>(); 
    int[] rank=new int[x.length]; // maximum length for already unique array 
    for(double d:x) 
     if (lst.indexOf(d) == -1) //only unique elements in list 
      lst.add(d); 

    Collections.sort(lst); 
    for(int i=0;i<x.length;i++) { 
     rank[i]=lst.indexOf(x[i]); 
    } 
    return rank; 
} 

Этот код дает следующий вывод

[3.0, 1.3, 2.0, 3.0] - original 
[2, 0, 1, 2] - should be 
[2, 0, 1, 2] - our rank 

Меня интересует лучшая реализация вышеуказанного кода. Как это можно сделать лучше?

Редактировать

Этого вопрос просит дублирующие элементы быть ранжированы аналогичным образом и непрерывно, т.е. {0,1,2,3,...}, не пропуская промежуточный ранг, который отличается от аналогичного, но другого вопроса How to find what is the rank of each element in an integer array. Этот вопрос требует вывода {3,0,1,3}, если задан вход {3,1,2,3}. то есть он обрабатывает повторяющиеся элементы по-разному или разбивает повторяющиеся значения на входе. Но это касается обработки дубликатов, и желаемый результат - {2,0,1,2}.

+0

Почему вы хотите удалить код из вопроса? – progyammer

+0

Как это можно сделать? Можете ли вы объяснить подробно? – Prabhu

+0

@progy_rock, это была опечатка при редактировании форматирования вопроса. Он был исправлен. – Prabhu

ответ

1

Я хотел бы пойти на такой подход:

public static int[] findRank(double[] inp) { 
    int[] outp = new int[inp.length]; 
    for(int i = 0; i < inp.length; i++) { 
     for(int k = 0; k < inp.length; k++) { 
      if(inp[k] < inp[i]) outp[i]++; 
     } 
    } 
    return outp; 
} 

я просто придумал это на лету, так что я не могу сказать на 100%, если это действительно быстрее, чем ваш путь, но я бы сказал, это выглядит лучше, и вам не нужно зависеть от Java-реализаций Collections.sort() и списков в целом.

+1

Это O (n^2), определенно не быстрее, чем оригинальный способ сделать это. – bilalba

+0

Это быстрее на массивах размером менее ~ 7000 – darkfire000

+0

Это решение работает, но, похоже, сложнее, чем мое решение. – Prabhu

1

Если вы ищете эффективность, не переходите на поиск индекса списка с list.indexOf() несколько раз. Сложность времени нахождения элемента в списке - O (n), как объясняется http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

Вы можете использовать Map вместо List. Поиск элемента по ключу в Map использует сложность O (1).

1

Предполагая, что тип O (n log (n)), то один проход O (n) будет генерировать уникальный ранг. Сортировка массива целых чисел I [] в соответствии с x [] с использованием lambda compare (lambda compare требует, чтобы I [] имел тип Integer). Затем сгенерируем единственный ранг R [] по I [] и x [].

// return unique rank 
private static int[] findRank(double[] x){ 
    int [] R = new int[x.length]; 
    if(x.length == 0)return R; 
    Integer [] I = new Integer[x.length]; 
    for(int i = 0; i < x.length; i++) 
     I[i] = i; 
    Arrays.sort(I, (i0, i1) -> (int) Math.signum(x[i0]-x[i1])); 
    int j = 0; 
    for(int i = 0; i < x.length; i++){ 
     if(x[I[i]] != x[I[j]]) 
      j = i; 
     R[I[i]] = j; 
    } 
    return R; 
} 
1

У вас есть некоторые проблемы с эффективностью в вашем коде. Первым и главным является использование array.indexOf(). Поиск индекса в массиве является дорогостоящим O (n). Вместо этого вы можете создать Map вместо массива и использовать x.get(key), чтобы получить ранг, связанный с этим. Вы можете определить и получить ключи в карте как:

Map<Double,Integer> x = new HashMap<Double, Integer>(); 
x.put(3.5,0); 
x.put(2.0,1); 
x.put(4.1,2); 
//.... and put following in loop 
y=x.get(2.0); //y=1 

Но использование удваиваются как key в HashMap можно сделать, но это может быть не очень хорошая идея, поскольку Double сравнения может иметь проблемы с плавающей точкой. Но основная идея - использовать стоимость O (1).