diff options
-rw-r--r-- | array_nesting.c | 37 | ||||
-rw-r--r-- | array_nesting.py | 32 |
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])) |