0

だから、私はこのような配列を持っています:

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;    
            }
        }
    }   
}
4

2 に答える 2

5

  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
于 2013-04-29T22:04:52.583 に答える
0

それを行うためのさらに効率の悪い方法として、1回のパススルーを実行して更新を続けます:)

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))
于 2013-04-30T16:21:08.603 に答える