算法——查找一个ip地址数组中,出现次数最多的ip
2021/10/16 14:09:27
本文主要是介绍算法——查找一个ip地址数组中,出现次数最多的ip,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一道算法题
找出一组ip地址中,出现次数最多的ip,例:
输入
["192.168.12.32", "192.168.0.32", "192.168.12.32"]
输出
"192.168.12.32"
暴力破解法
function filterIp(ipArr) { let maxIp = ''; let maxCount = 0; for(let i = 0; i < ipArr.length; i++) { let cur = ipArr[i]; let sum = 0; for(let j = 0; j < ipArr.length; j++) { if(cur === ipArr[j]){ sum++; } } if(sum > maxCount) { maxCount = sum; maxIp = cur; } } return maxIp; }
console.time() filterIp(arr) console.timeEnd() default: 0.9111328125 ms
哈希表
function filterIp(ipArr) { const map = {}; for(let i = 0; i < ipArr.length; i++) { // 如果map中存在当前ip的key值,则表示该ip已经被统计过了。 if(map[ipArr[i]]){ continue; } let cur = ipArr[i]; let sum = 0; // 从 i 开始,i 之前的一定是被统计过了的 for(let j = i; j < ipArr.length; j++) { if(cur === ipArr[j]){ sum++; } } // 写入map中 map[cur] = sum; } let max = 0; let maxIp= ''; for(let key in map){ if(map[key] > max){ max = map[key]; maxIp= key; } } return maxIp; }
console.time() filterIp(arr) console.timeEnd() default: 0.208740234375 ms
字典树搜索
class Node { constructor(data){ this.data = data; } data = ''; count = 1; leaf = []; addLeaf(leaf) { this.leaf.push(leaf); } findLeaf(data) { for(let i = 0; i < this.leaf.length; i++) { if(this.leaf[i].data === data){ return this.leaf[i]; } } return null; } addCount(){ this.count++; } } function createIpTree(ipArr){ // 根节点为空 let root = new Node(''); for(let i = 0; i < ipArr.length; i++){ let pointer = root; ipArr[i].split('.').forEach(item => { let includesLeaf = pointer.findLeaf(item); if(includesLeaf){ includesLeaf.addCount(); pointer = includesLeaf; } else { let node = new Node(item); pointer.addLeaf(node); pointer = node; } }) } return root; } function depthFirstSearch(pointer) { let maxLeaf = pointer.leaf[0]; for(let i = 0; i < pointer.leaf.length; i++) { if(pointer.leaf[i].count > maxLeaf.count){ maxLeaf = pointer.leaf[i]; } } return maxLeaf; } function filterIp(ipArr){ // 创建字典树 const ipTree = createIpTree(ipArr); // 深度优先搜索字典树,找出每个节点 count 最大的叶子,向下寻找 let pointer = ipTree; let strArr = []; while(pointer.leaf.length) { let maxLeaf = depthFirstSearch(pointer); pointer = maxLeaf; strArr.push(maxLeaf.data); } return strArr.join('.'); }
console.time() filterIp(arr) console.timeEnd() tree: 0.26220703125 ms
字典树居然没有哈希表快?????
哈希表我可能用的不太好,我感觉还有优化方法,不过没有深入去想了。
可能还有别的方法,不过我暂时就想到这三个了。
这篇关于算法——查找一个ip地址数组中,出现次数最多的ip的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现