找卧底

• 时间复杂度: o(n)
• 空间复杂度: o(1)
• 思路: 题目会给出一个乱序的数组，我们可以尝试将其恢复。我们假设牛牛的数在有序数组中排在第一个位置，即a[0]（牛牛这么牛，当然要排在最前面），然后其他的数依次递增排列，即n排在a[n]。则当我们拿到打乱顺序后的数组后，我们可以取出a[0]，假设此时a[0]=p，则可知这个数原先所在位置为a[p]，我们取出a[p]，比较a[p]是否等于p，如果不是我们将a[0]和a[p]的值互换重复操作，如果是则说明牛牛所代表的数就是p，卧底找到了。
• 代码实现

package nowcoder.pinnacle.s1.match3.gold;

/**
 * 找卧底
 * @Author: nayix
 * @Date: 7/21/20 10:58 AM
 */
public class ProblemA {

    /**
     *
     * @param n int整型
     * @param a int整型一维数组
     * @return int整型
     */
    public int search (int n, int[] a) {
        while (a[a[0]] != a[0]) {
            int p = a[0];
            a[0] = a[p];
            a[p] = p;
        }
        return a[0];
    }

    public static void main(String[] args) {
        ProblemA problemA = new ProblemA();
        System.out.println(problemA.search(4, new int[]{1, 2, 1, 4, 3}));
    }
}