1365. Minimum Cycle Section

Given an array of int, find the length of the minimum cycle section.
  • The length of array do not exceed 100000。
  • Each element is in the int range 。

Example

Example 1
Input: [1,2,1,2,1,2]
Output: 2
Explanation:
The minimum cycle section is [1,2],and the length is 2.
Example 2
Input: [1,2,1,2,1]
Output: 2
Explanation:
The minimum cycle section is [1,2],and the length is 2, although the last 2 is not given, we still consider the cycle section is [1,2].
Example 3
class Solution { public: /** * @param array: an integer array * @return: the length of the minimum cycle section */ int minimumCycleSection(vector<int> &array) { // Write your code here int *next = new int[array.size() + 1]; int i = 0, j = -1; next[0] = -1; while(i < array.size()) { if(j == -1 || array[i] == array[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } return i - next[i]; } };

Comments

Popular posts from this blog

算法的比较

生命