-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSort an Array.php
67 lines (59 loc) · 1.38 KB
/
Sort an Array.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
<?php
class Solution
{
function merge(&$la, &$ra, &$nums,&$ans)
{
$i = $j = $k = $f = 0;
$nla = count($la);
$nra = count($ra);
while ($i < $nla && $j < $nra) {
if ($la[$i] <= $ra[$j]) {
$nums[$k] = $la[$i];
$ans[$la[$i]]+=$f;
$i++;
$k++;
} else {
$nums[$k] = $ra[$j];
$j++;
$k++;
$f++;
}
}
while ($i < $nla) {
$ans[] += $f;
$nums[$k++] = $la[$i++];
}
while ($j < $nra) {
$nums[$k++] = $ra[$j++];
}
}
function mergeShort(&$nums,&$ans)
{
$l = count($nums);
if ($l < 2) return;
$mid = (int)($l / 2);
$la = [];
$ra = [];
for ($i = 0; $i < $mid; $i++) {
$la[$i] = $nums[$i];
}
for ($i = $mid; $i < $l; $i++) {
$ra[$i - $mid] = $nums[$i];
}
$this->mergeShort($la,$ans);
$this->mergeShort($ra,$ans);
$this->merge($la, $ra, $nums,$ans);
}
function sortArray($nums)
{
$ans=[];
$this->mergeShort($nums,$ans);
return $ans;
}
}
$obj = new Solution();
$cost = [5, 2, 6, 1];
// $cost = [-1,-1];
echo "<pre>";
print_r($obj->sortArray($cost));
echo "</pre>";