java - 在 Count 排序数组中查找中间元素

Question

所以，我有这样的数组：

a[1] = 2
a[4] = 3
a[8] = 1

代表这个序列1 1 4 4 4 8

我需要找到中间元素，或者之前的元素（奇偶）；在这个例子中，它是 4。

我怎样才能快速做到这一点？

我的代码很慢：

static int B(int[] array, int size) {       
    int c = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i]; j++) {
            c++;
            if (c == size / 2) {
                return i;    
            }
        }
    }   
}

Answer 1

1. 遍历原始数组并添加所有值

   a[1] = 2
   a[4] = 3
   a[8] = 1
   sum = 6
   

2. 将总和除以 2（求中位数）

   mid = 6/2 = 3
   

3. 遍历原始数组并从总和中减去值

   check if ans <= 0
   if true print index
   else continue to next
   

Answer 2

对于一种效率更低的方法，请运行一次并不断更新:)

Javascript（因为我受到 Java 挑战）：

var a=[]

a[1] = 2
a[4] = 3
a[8] = 1
a[9] = 2
a[10] = 3
a[11] = 1
//1 1 4 4 4 8 9 9 10 10 10 11

function middle (arr){
  var stack = [],
      total = 0,
      tmp,
      tmpChange,
      middle = 0,
      change = 0,
      middleElement

  for (i in arr){
    stack.push([i, arr[i]])
    total += arr[i]
    tmp = Math.ceil(total/2)
    change = tmp - middle
    middle = tmp

    while (change){
      tmpChange = stack[0][1] - change

      if (tmpChange >= 0) {
        stack[0][1] = tmpChange
        change = 0
      }
      else {
        change -= stack[0][1]
        stack.splice(0,1) 
      }
    }

    middleElement = stack[0][0]
  }

  return middleElement
}

console.log(middle(a))