Leetcode PHP题解--D98 697. Degree of an Array

D98 697. Degree of an Array

题目链接

697. Degree of an Array

题目分析

返回出现次数最多的元素的键差最小的值。

思路

先用array_count_values计算元素出现次数,用arsort排序。

再遍历该数组,记录第一个元素的值。用以记录最大值。

获取当前遍历元素在原数组中的最小下标和最大下标。其差值为所求数。

最后返回最小的该数即可。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findShortestSubArray($nums) {
        $elementCount = array_count_values($nums);
        $revNums = array_reverse($nums);
        $numAmounts = count($nums);
        arsort($elementCount);
        $minLength = 50000;

        $maxValue = key($elementCount);
        $maxAmount = current($elementCount);
        foreach($elementCount as $elk => $elv){
            if($elv<$maxAmount){
                break;
            }
            $left = array_search($elk, $nums);
            $right = $numAmounts - array_search($elk, $revNums)-1;
            if($right-$left+1 <$minLength){
                $minLength = $right-$left+1;
            }
        };

        return $minLength;
    }
}

本代码运行时间只超过了20%的提交。故肯定是有更优解的。

若觉得本文章对你有用,欢迎用爱发电资助。