coding everyday

编程面试题 https://interview.codeplex.com

C++博客 首页 新随笔 联系 聚合 管理
  12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks

#面试题#给定数组A,大小为n,数组元素为1n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么


想了好久,都没能想出来算法,我觉得是不是自己走进死胡同了,决定再看一遍题目,这一遍果然让我发现,原来自己真的理解错了题目的意思,我一开始以为要输出多次出现的数字对应的数字,所以一直都绕不过来弯。

所以有时候面试过程中,重新确认题目还是有必要的,有时候面试紧张会误解题目意思,当自己没有思路的时候,可以尝试确认题意,以来可以缓解一下自己的心情,再者可能面试官会跟你有更多的互动,增加好感。


确定了题意,基于之前的思考,我的算法是这样的遍历一遍数组,用-2,-1,0来表示没有出现,出现一次,出现多次,如果当前节点大于0,目标节点为它对应的值,当前置为-2,若小于0,加一但不要超过0。算法需要一个递归函数(用来递归处理目标节点一直大于0的情况,即未处理过的)和一个遍历的函数。最终0即为多次出现,-1出现1次的,-2没有出现。因为有2个前提这个算法才有效:1~n;只要出现多次和没出现的数字,不需要次数。

 

 1 #include <iostream>
 2 #include <array>
 3 using namespace std;
 4 
 5 template<int N>
 6 class array_stat {
 7 public:
 8     array_stat(const array<int, N>& arr) : m_arr(arr) {
 9     }
10 
11     void operator()() {
12         for (int i=1; i<=N; i++) {
13             process(i);
14         }
15 
16         for (int i=0; i<N; i++) {
17             if (m_arr[i] == 0)
18                 cout << i+1 << " exists more than once" << endl;
19             else if (m_arr[i] == -2)
20                 cout << i+1 << " doesnt exist" << endl;
21         }
22     }
23 private:
24     array<int, N> m_arr;
25 
26     void process(int i) {
27         if (m_arr[i-1> 0) {
28             int cur = m_arr[i-1];
29             m_arr[i-1= -2;
30             process(cur);
31         }
32         else {
33             m_arr[i-1]++;
34             if (m_arr[i-1> 0)
35                 m_arr[i-1= 0;
36         }
37     }
38 };
39 
40 int main() {
41     array<int10> arr = {2143565656};
42     array_stat<10> stat(arr);
43     stat();
44     return 0;
45 }

源代码
posted on 2013-08-29 10:24 everyday 阅读(686) 评论(0)  编辑 收藏 引用 所属分类: Algorithm面试

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理