лучший способ посчитать большие элементы на правой и левой стороне массива

Например, в php

$arr = [9, 4, 3, 5, 2, 6];

затем,

$output = [[0,0], [1,2], [2,2], [1,1], [4,1], [1,0]];
[0, 0] = большие элементы 9 равны 0 с обеих сторон

[1, 2] = большие элементы 4 равны 1 (9) слева и 2 (5, 6) справа … [9> 4] — [5> 4, 6> 4] [2, 2] = большие элементы 3 равны 2 (9, 4) слева и 2 (5, 6) справа

[1, 1] = большие элементы 5 равны 1 (9) слева и 1 (6) справа

[4, 1] = более крупные элементы 2 (9, 4, 3, 5) — 4 слева и 1 (6) справа

[1, 0] = большие элементы 6 равны 1 (9) слева и 0 (нет элементов после 6) справа

Я хочу это в O (n log (n)), это возможно?

0

Решение

Похоже, уже много ответов, вы можете сделать это с некоторыми функциями массива, как некоторые из ответов, но так как это, вероятно, для вашей домашней работы, чтобы было проще. Я отслеживаю, следует ли увеличивать влево и вправо каждую итерацию с помощью переменной $ side.

$arr = [9, 4, 3, 5, 2, 6];
$results = [];
for ($x = 0; $x < count($arr); $x++) {
$results[$x] = [0,0];
$side = 0;
for ($y = 0; $y < count($arr); $y++) {
if ($arr[$y] > $arr[$x]) {
$results[$x][$side]++;
} elseif ($arr[$x] == $arr[$y]) {
$side = 1;
}
}
}
0

Другие решения

Вам нужно перебрать $arr чтобы получить каждое значение, а затем, в цикле, снова цикл $arr чтобы получить другие значения. Затем во втором цикле вы строите свой выходной массив, сравнивая оба value (чтобы узнать, действительно ли число больше) и key (чтобы узнать, слева это или справа).

$arr = array(9, 4, 3, 5, 2, 6);
$output = array();
foreach ($arr as $key=>$value) {
$out = array(0, 0);
foreach ($arr as $key2=>$value2) {
if ($key2 == $key) # If it's the same element
continue;
if ($value2 > $value) {
if ($key2 < $key)
$out[0]++;
else
$out[1]++;
}
}
$output[] = $out;
}

print_r($output);

Смотрите вывод Вот.

0

Попробуй это:

function fix_array($array) {
$return_array = array();

foreach ($array as $i => $value){
$left = array_slice($array, 0, $i);

$count_left = count(array_filter($left, function($var) use($value){
return $var > $value;
}));

$right = array_slice($array, $i + 1);

$count_right = count(array_filter($right, function($var) use($value){
return $var > $value;
}));

$return_array[] = [$count_left, $count_right];

}

return $return_array;
}

$arr = [9, 4, 3, 5, 2, 6];

$new_array = fix_array($arr);

print_r($new_array);
0

Просто сравните его с левым и правым значениями. Попробуй это:

$arr = [9, 4, 3, 5, 2, 6];
$total = count($arr);

$new_arr=array();
foreach ($arr as $key => $value) {
$left = 0;
$right = 0;
for ($i=0; $i < $total; $i++) {
if($key > $i && $arr[$i] > $arr[$key])
{
$left++;
}
elseif ($key < $i && $arr[$i] > $arr[$key]) {
$right++;
}
}
$new_arr[]=[$left,$right];

}
echo "<pre>";
print_r($new_arr);
0

Попробуйте следующий код, используя array_walk ()

<?php

$arr = [9, 4, 3, 5, 2, 6];

$finalArray =[];
array_walk($arr, function($value,$key) use(&$finalArray,&$arr) {

$param ['pre_val']=0;
$param ['post_val']=0;
$param ['current_index'] = $key;
$param ['current_value'] = $value;
$arr2 = $arr;
array_walk($arr2, function(&$value,$key) use(&$finalArray,&$param) {
if($key < $param['current_index']){
if($value > $param['current_value']){$param['pre_val'] ++;}
}else{
if($value > $param['current_value']){$param['post_val'] ++;}
}
$finalArray[$param['current_index']][0] = $param['pre_val'];
$finalArray[$param['current_index']][1] = $param['post_val'];
});
});print_r($finalArray);
0