題目

You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].

You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:

  • The first element in s[k] starts with the selection of the element nums[k] of index = k.
  • The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
  • We stop adding right before a duplicate element occurs in s[k].

Return the longest length of a set s[k].

Example 1:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

Example 2:

Input: nums = [0,1,2]
Output: 1

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] < nums.length
  • All the values of nums are unique.

解題

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function arrayNesting($nums) {
        
        $result = 0;
        
        foreach($nums as $key => $val) {
            if (array_key_exists($key, $nums)) {
                $k = $nums[$key];
                unset($nums[$key]);
                $count = 1;
                
                while(array_key_exists($k, $nums)) {
                    $k = $nums[$k];
                    $count++;
                }
                
                $result = max($result, $count);
            }
        }
        
        return $result;
    }
}

Runtime: 127 ms, faster than 9.09% of PHP online submissions for Array Nesting.

Memory Usage: 18.4 MB, less than 77.27% of PHP online submissions for Array Nesting.

進階

/**
 * @param Integer[] $nums
 * @return Integer
 */
function arrayNesting($nums) {

    $result = 0;
    for ($i = 0; $i < count($nums); ++$i) {
        if ($nums[$i] != -1) {
            $count = 0;
            while($nums[$i] != -1) {
                $j = $nums[$i];
                $nums[$i] = -1;
                $i = $j;
                $count++;
            }
            $result = max($result, $count);
        }
    }

    return $result;
}

Runtime: 40 ms, faster than 79.17% of PHP online submissions for Array Nesting.

Memory Usage: 18.5 MB, less than 25.00% of PHP online submissions for Array Nesting.