Index or value based 2-pointer method?


  • 0

    I sense this question is somehow related to slow/fast pointer methods. However, as I was trying to approach this question with a method similar to Linked List Cycle question, I was trying to do p1=p1+1, and p2 = p2 +2 approach, as blow. Because in the Linked List Cycle problem, we each time move the slow & fast nodes based on the index (or more precisely, links, for linked list). Obviously it did not worked here. (past most test case though). Compared with @echoxiaolee solution. I am wondering why are we moving the slow & fast pointers based on values nums[p] = nums[nums[p]], not based on index like what I did?

    public class Solution {
        public int findDuplicate(int[] nums) {
         int p1= 0; 
         int p2 = 0; 
         do{
             if(p1+1 == nums.length){
                 p1 = 0;
             }else{
                 p1++; 
             }
             if(p2+2 == nums.length){
                 p2 = 0;
             }else if(p2 + 2 == nums.length + 1){
                 p2 = 1; 
             }else{
                 p2++; 
                 p2++; 
             }
         }while(nums[p1] != nums[p2] || p2==p1 ) ;
         return nums[p1]; 
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.