Find the Duplicate Number
双指针. 找环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class FloydsCycleDetection { public static int floyd(int[] a){ int s = a[0]; int f = a[0]; do { s = a[s]; f = a[a[f]]; } while (s!=f); s = a[0]; while (s != f){ s = a[s]; f = a[f]; } return f; } public static void main(String[] args) { int[] t = new int[]{1,3,4,2,2}; System.out.println(floyd(t)); } } |
Leave A Comment