算法题

发表于 2012-10-15 23:20

给出一个数组，已知元素的个数，数组中的元素是乱序的，要求在O(n)时间复杂度和O(1)空间复杂度条件下找出第一个唯一的元素。

例如数组是“5 31 5 88 67 88 17 ”，则这个元素是31（虽然31，67,17是唯一的元素，31是第一个出现的）
数组是“3 4 5 4 3 5”，则没有唯一元素

注意：“开辟一个数组，遍历数组，记录每个元素的出现次数”该方法不合题意，要求O(1)空间复杂度。

发表于 2012-10-15 23:41

如果输入数据有范围的话，直接申请该范围的次数数组和位置数组，虽然很大，但因为和输入数据的数量没关系，按照定义就是O(1)
遍历全部数据，如果出现数值a就将times[1]++，第一次出现时记录pos[a]，遍历输入数据后再遍历数据范围，就能得到结果

这种方法，在数据范围比输入数据个数大得多的时候一点实用意义都没有，但在正好相反的情况下也是有实用价值的

发表于 2012-10-15 23:50

难度不小

发表于 2012-10-17 20:50

挺复杂啊，得琢磨琢磨再说啦

算法题

相关帖子

浏览过的版块