leetcode 565. Array Nesting 最大的环的元素数量

╰半橙微兮° 2022-06-03 04:20 202阅读 0赞

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:
Input: A = [5,4,0,3,1,6,2]
Output: 6
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
Note:
N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of A is an integer within the range [0, N-1].

本题题意有点绕,本质上就是就求环的元素的数量,直接暴力求解即可,注意使用标志数组来处理

代码如下:

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <string>
  8. #include <climits>
  9. #include <algorithm>
  10. #include <sstream>
  11. #include <functional>
  12. #include <bitset>
  13. #include <numeric>
  14. #include <cmath>
  15. using namespace std;
  16. class Solution
  17. {
  18. public:
  19. int arrayNesting(vector<int>& nums)
  20. {
  21. int maxLen = 0;
  22. vector<bool> visit(nums.size(), false);
  23. for (int i = 0; i < nums.size(); i++)
  24. {
  25. if (visit[i] == false)
  26. {
  27. int j = i, count = 0;
  28. while (count == 0 || j != i)
  29. {
  30. visit[j] = true;
  31. j = nums[j];
  32. count++;
  33. }
  34. maxLen = max(maxLen,count);
  35. }
  36. }
  37. return maxLen;
  38. }
  39. };

发表评论

表情:
评论列表 (有 0 条评论,202人围观)

还没有评论,来说两句吧...

相关阅读