首页 / 软件开发 / 数据结构与算法 / 经典算法（11） 一道有趣的GOOGLE面试题 --【解法2】

经典算法（11） 一道有趣的GOOGLE面试题 --【解法2】2014-01-03 csdn MoreWindows上一篇《白话经典算法系列之十一道有趣的GOOGLE面试题》中对一道有趣的GOOGLE面试题进行了详细的讲 解，使用了类似于基数排序的做法在O（N）的时间复杂度和O（1）的空间复杂度完成了题目的要求，文章发表后 ，网友fengchaokobe在评论中给出了另一种解法，见下图。

文字版：

int Repeat（int *a, int n）{for（int i = 0; i < n; i++）{if（a[i] > 0） //判断条件{if（a[ a[i] ] < 0）{return a[i];//已经被标上负值了，有重复}else{a[ a[i] ]= -a[a[i]]; //记为负} }else // 此时|a[i]|代表的值已经出现过一次了{if（a[-a[i]] < 0）{return -a[i];//有重复找到}else{a[ -a[i] ] = -a[ -a[i] ];}}}return -1;//数组中没有重复的数}