KthSmallestElementInASortedMatrix::kthSmallest() - Code Metrics - imajinyun/leetcode-php - Measure and Improve Code Quality continuously with Scrutinizer

KthSmallestElementInASortedMatrix::kthSmallest() A
last analyzed 2022-03-29 06:17 UTC

↳ Parent: KthSmallestElementInASortedMatrix

Complexity

Conditions	6
Paths	5

Size

Total Lines	17
Code Lines	10

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	10
c	1
b	0
f	0
dl	0
loc	17
rs	9.2222
cc	6
nc	5
nop	2

<?php

declare(strict_types=1);

namespace leetcode;

class KthSmallestElementInASortedMatrix
{
    public static function kthSmallest(array $matrix, int $k): int
    {
        if (empty($matrix) || $k <= 0) {
            return 0;
        }
        $heap = new \SplMaxHeap();
        [$m, $n] = [count($matrix), count($matrix[0])];
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $heap->insert($matrix[$i][$j]);
                if ($heap->count() > $k) {
                    $heap->extract();
                }
            }
        }

        return $heap->top();
    }

    public static function kthSmallest2(array $matrix, int $k): int
    {
        if (empty($matrix) || $k <= 0) {
            return 0;
        }
        [$m, $n] = [count($matrix), count($matrix[0])];
        [$low, $high] = [$matrix[0][0], $matrix[$m - 1][$n - 1]];
        $helper = static function (array $matrix, int $target) {
            $n = count($matrix);
            [$cnt, $i, $j] = [0, $n - 1, 0];
            while ($i >= 0 && $j < $n) {
                if ($matrix[$i][$j] > $target) {
                    $i--;
                } else {
                    $cnt += ($i + 1);
                    $j++;
                }
            }
            return $cnt;
        };

        while ($low < $high) {
            $mid = (int)(($high - $low) / 2) + $low;
            $cnt = $helper($matrix, $mid);
            if ($cnt < $k) {
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        }

        return $low;
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			namespace leetcode;
6
7			class KthSmallestElementInASortedMatrix
8			{
9			public static function kthSmallest(array $matrix, int $k): int
10			{
11			if (empty($matrix) \|\| $k <= 0) {
12			return 0;
13			}
14			$heap = new \SplMaxHeap();
15			[$m, $n] = [count($matrix), count($matrix[0])];
16			for ($i = 0; $i < $m; $i++) {
17			for ($j = 0; $j < $n; $j++) {
18			$heap->insert($matrix[$i][$j]);
19			if ($heap->count() > $k) {
20			$heap->extract();
21			}
22			}
23			}
24
25			return $heap->top();
26			}
27
28			public static function kthSmallest2(array $matrix, int $k): int
29			{
30			if (empty($matrix) \|\| $k <= 0) {
31			return 0;
32			}
33			[$m, $n] = [count($matrix), count($matrix[0])];
34			[$low, $high] = [$matrix[0][0], $matrix[$m - 1][$n - 1]];
35			$helper = static function (array $matrix, int $target) {
36			$n = count($matrix);
37			[$cnt, $i, $j] = [0, $n - 1, 0];
38			while ($i >= 0 && $j < $n) {
39			if ($matrix[$i][$j] > $target) {
40			$i--;
41			} else {
42			$cnt += ($i + 1);
43			$j++;
44			}
45			}
46			return $cnt;
47			};
48
49			while ($low < $high) {
50			$mid = (int)(($high - $low) / 2) + $low;
51			$cnt = $helper($matrix, $mid);
52			if ($cnt < $k) {
53			$low = $mid + 1;
54			} else {
55			$high = $mid - 1;
56			}
57			}
58
59			return $low;
60			}
61			}
62

imajinyun / leetcode-php

KthSmallestElementInASortedMatrix::kthSmallest() A last analyzed 2022-03-29 06:17 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

KthSmallestElementInASortedMatrix::kthSmallest() A
last analyzed 2022-03-29 06:17 UTC