首页 > 代码库 > 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