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

Question

Как часть моего алгоритма QuickSort, я пытаюсь найти медианное значение у Arraylist с учетом индекса первого, среднего и последнего элементов. Я использовал несколько операторов if/else как способ их поиска, но это неправильно, и логика довольно запутана.

Примечание: Сортировка массива не является вариантом.

public static int findMedian(ArrayList <Integer> A, int first, int mid, int last) { 
    if(first == mid || first == last || last == mid) { 
     return first; 
    } 
    if(A.get(first) >= A.get(last)) { 
     if(A.get(first) <= A.get(mid)) { 
      return first; 
     } 
     else if(A.get(last) >= A.get(mid)) { 
      return last; 
     } 
     return mid; 
    } 
    else { 
     if(A.get(first) > A.get(mid)) { 
      return first; 
     } 
     else if(A.get(mid) > A.get(last)) { 
      return last; 
     } 
     return mid; 
    } 
} 

Answer 1

Одна вещь, которая выглядит странно, заключается в том, что если последняя == средняя, ​​вы сначала возвращаетесь.

Возможно, он будет работать лучше, если вы просто удалите строки:

if(first == mid || first == last || last == mid) { 
     return first; 
    } 

Answer 2

Что об этом методе?

public static int findMedian(ArarayList<Integer> A, int first, int mid, int \last) { 
    if (first == mid || first == last || last == mid) 
     return first; 

    int v = (A.get(first) >= A.get(mid) ? 1 : 0) + 
      (A.get(first) >= A.get(last) ? 2 : 0) + 
      (A.get(mid) >= A.get(last) ? 4 : 0); 

    switch (v) { 
    case 0: /* a < b && a < c && b < c */ 
     return mid; 
    case 1: /* a >= b && a < c && b < c */ 
     return first; 
    case 2: /* a < b && a >= c && b < c -> not possible */ 
     return -1; 
    case 3: /* a >= b && a >= c && b < c */ 
     return last; 
    case 4: /* a < b && a < c && b >= c */ 
     return last; 
    case 5: /* a >= b && a < c && b >= c -> not possible */ 
     return -1; 
    case 6: /* a < b && a >= c && b >= c */ 
     return first; 
    case 7: /* a >= b && a >= c && b >= c */ 
     return mid; 
    } 

    /* won't come here */ 
    return first; 
} 

Или в более компактном виде.

public static int findMedian(ArarayList<Integer> A, int first, int mid, int \last) {  
    if (first == mid || first == last || last == mid) 
     return first; 

    int result[] = new int[] { mid, first, -1, last, last, -1, first, mid }; 

    int v = (A.get(first) >= A.get(mid) ? 1 : 0) + 
      (A.get(first) >= A.get(last) ? 2 : 0) + 
      (A.get(mid) >= A.get(last) ? 4 : 0); 

    return result[v]; 
} 

Answer 3

возможность использовать Arrays.sort на своих индексов (я понимаю, вы не можете использовать вид на сам список) Вы? В этом случае вы можете просто сортировать индексы по значению, а затем выбрать один средний:

int findMedian(List<Integer> list, int first, int mid, int last) { 
    int[] indices = {first, mid, last}; 
    Arrays.sort(indices, (i1, i2) -> list.get(i1) - list.get(i2)); 
    return indices[1]; 
} 

Если вы не можете использовать сортировки по какой-либо причине, то вы можете сделать свой собственный простой вставки вид:

int findMedian(List<Integer> list, int first, int mid, int last) { 
    List<Integer> indices = new ArrayList<>(); 
    for (int i: Arrays.asList(first, mid, last) { 
     int j = 0; 
     while (j < indices.size() && list.get(i) > list.get(j)) 
      j++; 
     indices.add(j, i); 
    } 
    return indices.get(1); 
} 

Если вы не хотите использовать один из тех, то я предлагаю сделать ваше if заявления полностью явным:

if (list.get(first) >= list.get(mid) && list.get(first) <= list.get(last)) { 
    return first; 
else if (list.get(mid) >= list.get(first) && list.get(mid) <= list.get(last)) { 
    return mid; 
} else { 
    return last; 
}