首页 > 代码库 > Twitter OA prepare: Visit element of the array
Twitter OA prepare: Visit element of the array
A zero-indexed array A consisting of N integers is viven. We visit the indexs of the array in the following way. In the first step we visit the index 0; in every subsequent step we move from the visited index K to the index:M = K + A[K];provided M is within the array bounds. Otherwise, K is the last index visited. Write a funciton:int solution(int A[], int N);that, given an array A, returns the number of indexes that cannot be visited by the described procedure.For example, for the array:A[0] = 1A[1] = 2A[2] = 3only index 2 cannot be visited, so the answer is 1.For the array:A[0] = 3A[1] = -5A[2] = 0A[3] = -1A[4] = -3indexes 1 and 4 cannot be visited, so the answer is 2.Assume that:N is an integer within the range [0...200,000];each element of array A is an integer within the range [-1,000,000...1,000,000]Complexity:expected worst-case time complexity is O(N*log(N));expected worst-case space complexity is O(N*log(N)), beyond input storage (not counting the storage required for input arguments).Elements of input arrays can be modified.
分析:就是建立一个boolean array来记录array里面每个元素的访问情况,遇到访问过的元素就停止visiting,返回未访问的结点个数
1 public int visiting(int[] A, int N) { 2 if (A==null || A.length==0) return 0; 3 int cur = 0; 4 int count = 0; 5 boolean[] visited = new boolean[N]; 6 while (cur>=0 && cur<A.length && !visited[cur]) { 7 visited[cur] = true; 8 cur = cur + A[cur]; 9 count++;10 }11 return N-count;12 }
Twitter OA prepare: Visit element of the array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。