aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--array_nesting.c37
-rw-r--r--array_nesting.py32
2 files changed, 69 insertions, 0 deletions
diff --git a/array_nesting.c b/array_nesting.c
new file mode 100644
index 0000000..f56e72c
--- /dev/null
+++ b/array_nesting.c
@@ -0,0 +1,37 @@
+// 565. Array Nesting
+#include "leetcode.h"
+
+/*
+ * 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 bild a set
+ * 's[k] = {nums[k], nums[nums[k]], ... }' subjected to the following rules: 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 so on.
+ * we stop adding right before a duplication element occurs in 's[k]'. return
+ * the longest set of 's[k]'
+ */
+
+int arrayNesting(int *nums, int numsSize) {
+ int max = 0, cnt = 0;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i] != -1) {
+ int j = nums[i];
+ cnt = 0;
+ while (j != i) {
+ cnt++;
+ int tmp = nums[j];
+ nums[j] = -1;
+ j = tmp;
+ }
+ cnt++;
+ if (cnt > max)
+ max = cnt;
+ }
+ return max;
+}
+
+int main() {
+ int n1[] = {5, 4, 0, 3, 1, 6, 2}, n2[] = {0, 1, 2};
+ printf("%d\n", arrayNesting(n1, ARRAY_SIZE(n1))); // expect: 4
+ printf("%d\n", arrayNesting(n2, ARRAY_SIZE(n2))); // expect: 1
+}
diff --git a/array_nesting.py b/array_nesting.py
new file mode 100644
index 0000000..3cec7f5
--- /dev/null
+++ b/array_nesting.py
@@ -0,0 +1,32 @@
+# 565. Array Nesting
+
+"""
+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 bild a set
+'s[k] = {nums[k], nums[nums[k]], ... }' subjected to the following rules: 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 so on.
+we stop adding right before a duplication element occurs in 's[k]'. return
+the longest set of 's[k]'
+"""
+
+
+class Solution(object):
+ def arrayNesting(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ seen, ans = [0] * len(nums), 0
+ for i in nums:
+ cnt = 0
+ while not seen[i]:
+ seen[i], cnt, i = 1, cnt + 1, nums[i]
+ ans = max(ans, cnt)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.arrayNesting(nums=[5, 4, 0, 3, 1, 6, 2]))
+ print(obj.arrayNesting(nums=[0, 1, 2]))