Welcome to Subscribe On Youtube
-
/** A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1]. Sets S[K] for 0 <= K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets S[K] are finite for each K and should NOT contain duplicates. Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array. Example 1: Input: A = [5,4,0,3,1,6,2] Output: 4 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 array A is an integer within the range [0, N-1]. reference: https://leetcode.com/articles/array-nesting/ */ public class Array_Nesting { public class Solution_skip_visited { public int arrayNesting(int[] nums) { boolean[] visited = new boolean[nums.length]; int res = 0; for (int i = 0; i < nums.length; i++) { // @note: if visited, then the count here must be less than previous visit if (!visited[i]) { int start = nums[i], count = 0; do { start = nums[start]; count++; visited[start] = true; } while (start != nums[i]); res = Math.max(res, count); } } return res; } } public class Solution_brute_force { public int arrayNesting(int[] nums) { int res = 0; for (int i = 0; i < nums.length; i++) { int start = nums[i], count = 0; do { start = nums[start]; count++; } while (start != nums[i]); // if not the initial start number, then continue res = Math.max(res, count); } return res; } } } ############ class Solution { public int arrayNesting(int[] nums) { int ans = 0, n = nums.length; for (int i = 0; i < n; ++i) { int cnt = 0; int j = i; while (nums[j] < n) { int k = nums[j]; nums[j] = n; j = k; ++cnt; } ans = Math.max(ans, cnt); } return ans; } }
-
// OJ: https://leetcode.com/problems/array-nesting/ // Time: O(N) // Space: O(1) class Solution { public: int arrayNesting(vector<int>& A) { int ans = 0; for (int i = 0; i < A.size(); ++i) { if (A[i] == -1) continue; int cnt = 0, j = i; while (A[j] != -1) { int k = j; j = A[j]; A[k] = -1; ++cnt; } ans = max(ans, cnt); } return ans; } };
-
class Solution: def arrayNesting(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(n): cnt = 0 while nums[i] != n: j = nums[i] nums[i] = n i = j cnt += 1 ans = max(ans, cnt) return ans ############ class Solution(object): def arrayNesting(self, nums): """ :type nums: List[int] :rtype: int """ cache = [0] * len(nums) ans = 0 for i, start in enumerate(nums): if cache[i]: continue p = start length = 1 while nums[p] != start: cache[nums[p]] = 1 p = nums[p] length += 1 ans = max(ans, length) return ans
-
func arrayNesting(nums []int) int { ans, n := 0, len(nums) for i := range nums { cnt, j := 0, i for nums[j] != n { k := nums[j] nums[j] = n j = k cnt++ } if ans < cnt { ans = cnt } } return ans }
-
class Solution { public int arrayNesting(int[] nums) { int length = nums.length; boolean[] visited = new boolean[length]; int maxLength = 0; for (int i = 0; i < length; i++) { if (visited[i]) continue; int curLength = 0; int index = i; while (!visited[index]) { int num = nums[index]; visited[index] = true; index = num; curLength++; } maxLength = Math.max(maxLength, curLength); } return maxLength; } } ############ class Solution { public int arrayNesting(int[] nums) { int ans = 0, n = nums.length; for (int i = 0; i < n; ++i) { int cnt = 0; int j = i; while (nums[j] < n) { int k = nums[j]; nums[j] = n; j = k; ++cnt; } ans = Math.max(ans, cnt); } return ans; } }
-
// OJ: https://leetcode.com/problems/array-nesting/ // Time: O(N) // Space: O(1) class Solution { public: int arrayNesting(vector<int>& A) { int ans = 0; for (int i = 0; i < A.size(); ++i) { if (A[i] == -1) continue; int cnt = 0, j = i; while (A[j] != -1) { int k = j; j = A[j]; A[k] = -1; ++cnt; } ans = max(ans, cnt); } return ans; } };
-
class Solution: def arrayNesting(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(n): cnt = 0 while nums[i] != n: j = nums[i] nums[i] = n i = j cnt += 1 ans = max(ans, cnt) return ans ############ class Solution(object): def arrayNesting(self, nums): """ :type nums: List[int] :rtype: int """ cache = [0] * len(nums) ans = 0 for i, start in enumerate(nums): if cache[i]: continue p = start length = 1 while nums[p] != start: cache[nums[p]] = 1 p = nums[p] length += 1 ans = max(ans, length) return ans
-
func arrayNesting(nums []int) int { ans, n := 0, len(nums) for i := range nums { cnt, j := 0, i for nums[j] != n { k := nums[j] nums[j] = n j = k cnt++ } if ans < cnt { ans = cnt } } return ans }