FOJ 1001 Duplicate Pair （位图算法）

本文主要是介绍FOJ 1001 Duplicate Pair （位图算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

FOJ 1001 Duplicate Pair （位图算法）

Problem 1001 Duplicate Pair

Accept: 5374    Submit: 25613
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

An array of length n, with address from 1 to n inclusive, contains entries from the set {1,2,...,n-1} and there's exactly two elements with the same value. Your task is to find out the value.
 

Input

Input contains several cases.
Each case includes a number n (1<n<=10^6), which is followed by n integers.
The input is ended up with the end of file.
 

Output

Your must output the value for each case, one per line.

Sample Input

21 141 2 3 2

Sample Output

12 

题意：输入一串数字，这些数字都几乎只出现一次，但有些数字会出现俩次，找出这些数字并把它们打印出来。常规做法找俩个相同的数字用俩层循环，但是这样我试了会超时，所以我们只能开一个数组，方法有俩种，可以用位图算法，这是我做了这道题才学会的一种新算法，还有一种是桶排序也可以解决这个问题，大体就是这样吧。桶排序我就不说了，这里着重看一下位图算法吧。用一个数组a记录这些数，先吧a数组归0，如果a[j]==0，证明之前没有出现这个数，一旦出现将它设为1，如果这个数之前就a[j]==1

,证明之前已经有这个数了，把他打印出来就OK了。

#include<stdio.h>
int a[1000010];
int main()
{int n;while(~scanf("%d",&n)){int j;for(int i=0; i<n; i++){a[i]=0;}for(int i=0; i<n; i++){scanf("%d",&j);if(a[j]==0){a[j]=1;}else{printf("%d\n",j);}}}return 0;
}

但是这个题有个大坑啊，我陷在里面好久了，整整交了10次还是错，前一次是因为我用了俩层循环超时了，后面的几次全是Runtime Error这个错误，很是尴尬啊，我想了老长时间才发现的，原来是数组太大得开在外面，为啥呢，因为开在外面是全局的数组，计算机为其开辟的内存空间更大。这样就不会出现内存访问违规这个运行错误了。

 

 

这篇关于FOJ 1001 Duplicate Pair （位图算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---