Array: [1,2,3,4,2,3,2,2] randomly select 2 numbers in the array, there are 2 duplicate number schemes:

Violence loop method: double traverse the array, outer loop to find num1, and then inner loop, num2, find the nearest distance, when the loop ends, can be.

Copy the code

function misDistance(arr,num1,num2){ var len = arr.length; if(! Arr | | len < = 0) {return = 0} / / find short var minidis = arr. Dist = 0 for length – 1 var I = 0; i<len; ++ I){if(arr[I]==num1){for(arr[j]==num2){dist= math.abs (i-j) if(dist<minidis) minidis =dist}}

}
Copy the code

} because of the two traversal, so the time complexity n quadratic dynamic loop method of the above method 1, the inner loop for num2 position repeated many times, However, dynamic programming can be used to record the results of each iteration so as to reduce the number of iterations. Two cases: 1, when num1 is encountered, record the position of the array subscript corresponding to the value of num1 lastPost1, by finding the difference between lastPost1 and lastPost2, we can find the distance between num1 and num2 in the last traversal. When num2 is encountered, Also record the position of its array subscript lastpost2, and then find the distance between num1 and num2 last time by finding lastpost2 and the last time you traversed num1 subscript lastpost1.

Function minNum(x,y){return(x<y)? x:y } function miniDistance(arr,num1,num2){ var len = arr.length; if(! arr|| len<= 0){ return } var lastpost1 = -1; lastpost2 = -1 miniDinstance= arr.length; For (var I =0; i<len ; If (arr[I] == num1){arr[I] == num1; if(lastpost2>0){ minidistance = miniNum(miniDinstance,lastPost1-lastpost2) } } if(arr[i] == num2){ lastpost2= i; if(lastpost1>0){ minidistance = miniNum(miniDinstance,lastPost2-lastpost1) } } } return miniDis }Copy the code