计算数组右侧和左侧较大元素的最佳方法
best way to count the bigger elements on the right and left side of an array
例如,在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)) 的时间,可以吗?
您需要循环遍历 $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);
查看输出 here。
试试这个:
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);
简单比较一下左右值。试试这个:
$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);
使用 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);
看起来已经有很多答案了,您可以像某些答案那样使用一些数组函数来完成此操作,但由于这可能是您的家庭作业,所以最好保持简单。我通过使用 $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;
}
}
}
例如,在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)) 的时间,可以吗?
您需要循环遍历 $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);
查看输出 here。
试试这个:
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);
简单比较一下左右值。试试这个:
$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);
使用 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);
看起来已经有很多答案了,您可以像某些答案那样使用一些数组函数来完成此操作,但由于这可能是您的家庭作业,所以最好保持简单。我通过使用 $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;
}
}
}