Array Nesting

Mar 12, 2019

第12天。

今天的题目是565. Array Nesting

总感觉这道题是刷过的。这道题的输入是一个由0到 N-1 组成的数组,按照S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } 的规则,找到S[i]最长的长度。

显然按这种走法,这个数组会是由多个环组成的,也就是我们要找出最长那个环的长度,我们只需要简单的去寻找即可,而且一旦我们经过了某个元素,一定不会出现在其他人的环中了,所以我们可以将其赋值为-1表示已经使用过来。

这样,我们的算法就是O(n)的复杂度了:

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        
        int res = 0;
        for(int i = 0;i < nums.size(); i++) {
            if (nums[i] < 0) continue;
            res = max(res, helper(nums, i));
        }
        return res;
    }
    
    int helper(vector<int> &nums, int index) {
        int c = 0, j = nums[index];
        nums[index] = -1;
        while(j >= 0) {
            int t = nums[j];
            nums[j] = -1;
            j = t;
            c++;
        }
        return c;
    }
};
LeetCodeLeetCode

Stone Game

Bitwise ORs of Subarrays

comments powered by Disqus