已知一个整数序列\(A(a_0, a_1, \cdots, a_{n - 1})\)，该序列中有一个_

[数据结构 P2114] 已知一个整数序列\(A(a_0, a_1, \cdots, a_{n - 1})\)，该序列中有一个

学习人数: 134

正确率: 100%

题目描述

未通过

（13分）已知一个整数序列\(A(a_0, a_1, \cdots, a_{n - 1})\)，该序列中有一个元素只出现一次，其他元素都会出现两次，且相同元素一定相邻。请设计一个在时间上尽可能高效的算法，找出仅出现一次的元素。例如，数组\(\{3,3,6,6,9,0,0\}\)，则返回\(9\)。要求：

(1) 给出算法的基本设计思想。（3分）

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（8分）

(3) 说明你的算法的时间复杂度。（2分）

上一题

下一题

加入错题本

个人笔记

登录后提交答案

暂无评论，来抢沙发

参考答案

(1) 顺序遍历坐标为偶数的元素，...

用户登录可进行刷题及查看答案

(1) 顺序遍历坐标为偶数的元素，与后一个元素比较，如果前一个元素与后一个元素不一样，则前一个元素为目标值。

(2) 算法实现：

int func(int *A, int n) {
    for (int i = 0; i < n - 1; i += 2) {
        // 每次比较一对数字,不相等则前一个元素为目标元素
        if (A[i] != A[i + 1]) { return A[i]; }
    }
    return A[n-1]; // 最后一个元素为目标元素
}

(3) 算法中需要顺序遍历数组，时间复杂度为O(n)。