- 浏览: 717044 次
- 性别:
- 来自: 北京
最新评论
-
wxweven:
Surmounting 写道既然 Java 的跳表那么少,我决 ...
SkipList 跳表 -
暮雪云然:
写的不错,很透彻
Java静态内部类 -
bzhao:
好,赞扬!
Linux信号详解 -
jacktao219:
赞一个~! ,现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon:
vote--后还要判断是否为0吧,如果为0则废掉重新置位can ...
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
算法过程:
1 将顶点按x坐标递增排序,若x相同,按y坐标递增排序,然后枚举所有边,对每一条由点p1和p2(根据排序p1 < p2)组成的边按照如下方式可唯一确定一个正方形:
1) 将边绕p1逆时针旋转90度得到点p3
2) 将边绕p2顺时针旋转90度得到点p4
则p1 p2 p3 p4组成一个正方形,设p1 = (x1,y1), p2 = (x2, y2),根据向量的旋转公式可以求出p3, p4的坐标为
p3 = (y1 - y2 + x1, x2 - x1 + y1)
p4 = (y1 - y2 + x2, x2 - x1 + y2)
2 然后搜索点p3和p4是否存在,若存在则找到一个正方形,计数加1,可以发现总是存在两条边确定的正方形是一样的,也就是说每个正方形会被发现2次,所以要将最后的计数结果除以2.
实现的时候关键是如何搜索某个点是否存在,由于所有点都排序过,所以可以用二分查找来搜索,但速度比较慢,至少1000ms, hash的速度更快些,可以达到几百ms,还有hash表如果用开放地址线性探测法解决冲突的话,很容易超时,
而用链地址法解决冲突效果要好很多。下面是二分搜索和hash两种方法的代码实现。
二分查找
#include <stdio.h> #include <string.h> //#define DEBUG #ifdef DEBUG #define debug(...) printf( __VA_ARGS__) #else #define debug(...) #endif #define N 1000 struct Point { int x; int y; }; struct Point point[N]; int n; /* 点的个数 */ /* 由于点已经按照坐标排序过,所以采用二分查找 * 搜索点(x,y)是否存在,存在返回1,否则返回0 */ int bsearch(int x, int y) { int m, s, t; s = 0; t = n-1; while (s <= t) { m = (s+t)/2; if (point[m].x == x && point[m].y == y) return 1; if (point[m].x > x || (point[m].x == x && point[m].y > y)) { t = m-1; } else { s = m+1; } } return 0; } int main() { int x, y, i, j, count; while (scanf("%d", &n), n) { count = 0; for (i = 0; i < n; i++) { scanf("%d %d", &x, &y); //插入法对点排序,按照x从小到大,y从小到大,且x优先排列的方式 for (j = i-1; j >= 0; j--) { if (point[j].x > x || (point[j].x == x && point[j].y > y)) { point[j+1] = point[j]; } else { break; } } point[j+1].x = x; point[j+1].y = y; } /* 枚举所有边,对每条边的两个顶点可以 * 确定一个唯一的正方形,并求出另外两个顶点的坐标 */ for (i = 0; i < n; i++) { for (j = (i+1); j < n; j++) { //计算第三个点的坐标,搜索其是否存在 x = point[i].y-point[j].y+point[i].x; y = point[j].x-point[i].x+point[i].y; if (bsearch(x,y) == 0) { continue; } //计算第四个点的坐标,搜索其是否存在 x = point[i].y-point[j].y+point[j].x; y = point[j].x-point[i].x+point[j].y; if (bsearch(x, y)) { count++; } } } printf("%d\n", count/2); } return 0; }
hash
#include <stdio.h> #include <string.h> #include <stdlib.h> #define DEBUG #ifdef DEBUG #define debug(...) printf( __VA_ARGS__) #else #define debug(...) #endif #define N 1000 /* 顶点个数 */ #define M 2999 /* hash表的大小,取素数冲突冲突较少 */ struct Point { int x; int y; }; struct Point point[N]; /* 使用链地址法解决冲突, 表头不存数据 */ struct hash_entry { int x; int y; struct hash_entry *next; }; struct hash_entry hash_table[M+1]; int conflict; void insert(int x, int y) { unsigned int p; struct hash_entry *new_entry; p = (x*x+y*y)%M; /* hash函数 */ //创建一个新的entry new_entry = (struct hash_entry *)malloc(sizeof(struct hash_entry)); new_entry->x = x; new_entry->y = y; /* 把新entry插在最前面,这样,越先插进来的entry在链表的越后面, *最后一个entry的next指针为空 */ new_entry->next = hash_table[p].next; hash_table[p].next = new_entry; } int find(int x, int y) { unsigned int p; struct hash_entry *entry; p = (x*x+y*y)%M; /* hash函数 */ for(entry = hash_table[p].next; entry != 0 && (entry->x != x \ || entry->y != y); entry = entry->next, conflict++); if (entry) { return 1; } return 0; } int main() { int n, x, y, i, j, count; while (scanf("%d", &n), n) { memset(hash_table, 0, sizeof(hash_table)); count = 0; for (i = 0; i < n; i++) { scanf("%d %d", &x, &y); //插入法对点排序,按照x从小到大,y从小到大,且x优先排列的方式 for (j = i-1; j >= 0; j--) { if (point[j].x > x || (point[j].x == x && point[j].y > y)) { point[j+1] = point[j]; } else { break; } } point[j+1].x = x; point[j+1].y = y; insert(x, y); } /* 枚举所有边,对每条边的两个顶点可以 * 确定一个唯一的正方形,并求出另外两个顶点的坐标 */ for (i = 0; i < n; i++) { for (j = (i+1); j < n; j++) { //计算第三个点的坐标,搜索其是否存在 x = point[i].y-point[j].y+point[i].x; y = point[j].x-point[i].x+point[i].y; if (!find(x, y)) { continue; } //计算第四个点的坐标,搜索其是否存在 x = point[i].y-point[j].y+point[j].x; y = point[j].x-point[i].x+point[j].y; if (find(x, y)) { count++; } } } printf("%d\n", count/2); } debug("conflict = %d\n", conflict); return 0; }
发表评论
-
Paxos算法
2012-04-18 10:59 2483分布式系统的核心问题是数据一致性,解决一致性有很多算法,而 P ... -
编程之美3.3 计算字符串的相似度
2012-03-13 23:26 33问题描述 定义一套操作方法, 把两个不相同的字符串变得相同, ... -
编程之美3.1 字符串移位包含的问题
2012-03-12 23:26 3260题目 给定两个字符串 s ... -
SkipList 跳表
2011-10-09 01:08 39254为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树, ... -
(转)一致性哈希算法及其在分布式系统中的应用
2011-09-29 19:02 2270原文地址: http://www.cnb ... -
算法导论习题 5.1 -2
2011-09-29 09:23 1961描述random(a, b)过程的一种实现,它只调用rando ... -
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
2011-05-05 19:43 6166现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n ... -
从海量数据中找中位数(c语言实现)
2011-05-05 12:49 4986题目:5亿个int,从中找出第k大的数 算法:之后补上 ... -
寻找最大的K个数 (C语言实现)
2011-05-04 16:31 5288题目:100亿个整数,求最大的1万个数,并说出算法的时间复杂度 ... -
kmp算法的理解与实现
2011-04-30 21:29 25412KMP算法曾被我戏称为看毛片算法,当时笑喷...... ... -
败者树 多路平衡归并外部排序
2011-04-25 21:52 10505一 外部排序的基本思路 ... -
实现两个整数的除法,不能用除号和乘号
2011-04-22 15:17 3594对于两个整数a和b, 求a/b,可以从1开始枚举结果resul ... -
最大公共子字符串(Longest Common Substring)
2011-04-22 13:33 3342Longest Common Substring和Longes ... -
poj 1458 最长公共子串(Longest Common Subsequence)
2011-04-22 10:45 2517LCS问题: 给定序列 X = <x1,x2,... ... -
归并排序
2011-04-21 21:51 1138#include <stdio.h> #i ... -
快速排序 顺序统计量 数组分割
2011-04-21 19:28 1332#include <stdio.h> #in ... -
位运算集锦
2011-04-21 17:15 2045文中2'k代表2的k次方 1 除以2的k次幂可以用位运 ... -
最长递增子序列
2011-04-21 14:45 1155设L = <a1,a2,...an>是n个不同的实 ... -
poj 2774 后缀数组
2011-03-21 17:28 1743#include <stdio.h> # ... -
poj 2823 线段树
2011-03-17 18:49 1570赤裸裸的线段树,数据量很大,加了IO优化函数。 #in ...
相关推荐
北大POJ2002-Squares 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
poj 百练 题目分类 poj 百练 题目分类
poj分类poj分类poj分类poj分类
pojACM题目分类,便于各类型同学分别做题有所参考
POJ题目分类POJ题目分类POJ题目分类
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj题目分类
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
史上最全poj题目分类(159页).pdf
poj 1064 代码,二分查找的应用,没啥说的,看看
POJ题解及题目分类,共150道左右。C/C++
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。