C/C++ 查找算法

news/2024/12/15 9:22:54/

一.二分算法

调整:

如果arr[mid] < x, min = mid + 1;

如果arr[mid] > x, max = mid - 1;

如果arr[mid] == x, 找到结果

终止条件:min >= max

二分查找--泛型情况

找第一个1:

找最后一个1:

注意:mid = (min + max + 1) /2

代码演示:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>using namespace std;void output(int* arr, int n, int ind = -1) {int len = 0;for (int i = 0; i < n; i++) {len += printf("%4d", i);}printf("\n");for (int i = 0; i < len; i++) {printf("-");}printf("\n");for (int i = 0; i < n; i++) {if (i == ind) printf("\033[1;32m");printf("%4d", arr[i]);if (i == ind) printf("\033[0m");}printf("\n");return;
}int binary_search(int* arr, int n, int x) {int head = 0, tail = n - 1, mid;while (head <= tail) {mid = (head + tail) / 2;if (arr[mid] == x) return mid;if (arr[mid] < x) head = mid + 1;else tail = mid - 1;}return -1;
}void test_binary_search(int n) {int* arr = (int*)malloc(sizeof(int) * n);arr[0] = rand() % 10;for (int i = 1; i < n; i++) arr[i] = arr[i - 1] + rand() % 10;output(arr, n);int x;while (~scanf("%d", &x)) {if (x == -1) break;int ind = binary_search(arr, n, x);output(arr, n, ind);}
}#define EXP 1e-4double f(double x) {if (x >= 0) x -= min(x, 3000.0) * 0.03;if (x >= 3000) x -= (min(x, 12000.0) - 3000) * 0.1;if (x >= 12000) x -= (min(x, 25000.0) - 12000) * 0.2;if (x >= 25000) x -= (min(x, 35000.0) - 25000) * 0.25;if (x >= 35000) x -= (min(x, 55000.0) - 35000) * 0.3;if (x >= 55000) x -= (min(x, 80000.0) - 55000) * 0.35;if (x >= 80000) x -= (x - 80000) * 0.45;return x;
}double binary_algorithm(double y) {double head = 0, tail = 1000000, mid;while (tail - head >= EXP) {mid = (head + tail) / 2;if (f(mid) < y) head = mid;else tail = mid;}return head;
}void test_binary_algorithm() {double y;while (~scanf("%lf", &y)) {if (y < 0) break;double x = binary_algorithm(y);printf("f(%.2lf) = %.2lf\n", x, y);}
}int main() {
#define MAX_N 10test_binary_search(MAX_N);test_binary_algorithm();return 0;
}

二.跳跃表

对于原有链表中,对每个节点都设置了一个层高;

头节点的值为一个极小值,尾节点的值为一个极大值.

跳跃表本身,会维护节点中值的有序性

查找操作:

从左上角的节点开始查找:

若下一个节点的值比要查找的值大,则向下走一层;

若下一个节点的值比要查找的值小,则走向下一个节点;

插入操作:

跳跃表的每一个节点会随机一个层高

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<inttypes.h>typedef struct Node {int key, level;struct Node* next, * down, * up;
}Node;#define min(a,b) ((a) < (b) ? (a) : (b))
#define MAX_LEVEL 32
typedef struct Skiplist {Node* head, * tail;int max_level;
}Skiplist;Node* getNewNode(int key, int n) {Node* nodes = (Node*)malloc(sizeof(Node) * n);for (int i = 0; i < n; i++) {nodes[i].key = key;nodes[i].level = i;nodes[i].next = NULL;nodes[i].down = ((i != 0)? nodes + i - 1 : NULL);nodes[i].up = ((i + 1 < n)? nodes + i + 1 : NULL);}return nodes + n - 1;
}Skiplist* getNewSkiplist(int n) {Skiplist* s = (Skiplist*)malloc(sizeof(Skiplist));s->head = getNewNode(INT32_MIN, n);s->tail = getNewNode(INT32_MAX, n);s->max_level = n;Node* p = s->head, *q = s->tail;while (p) {p->next = q;p = p->down;q = q->down;}while (s->head->level != 0) s->head = s->head->down;return s;
}Node* find(Skiplist* s, int x) {Node* p = s->head;while (p && p->key != x) {if (p->next->key <= x) p = p->next;else p = p->down;}return p;
}#define MAX_RAND_N 10000double randDouble() {int n = (rand() % MAX_RAND_N);return (n * 1.0 / (double)MAX_RAND_N);
}int randLevel(Skiplist* s) {int level = 1;double p = 1.0 / 2.0;double temp = randDouble();while (temp < p) {level += 1;temp = randDouble();}return min(s->max_level, level);
}void insert(Skiplist* s, int x) {int level = randLevel(s);while (s->head->level + 1 < level) {s->head = s->head->up;}Node* node = getNewNode(x, level);Node* p = s->head;printf("insert begin\n");fflush(stdout);while(p->level != node->level) p = p->down;while (p) {while (p->next->key < node->key) p = p->next;node->next = p->next;p->next = node;p = p->down;node = node->down;}return;}void clearNode(Node* p) {if (p == NULL) return;free(p);return;
}void clearSkiplist(Skiplist* s) {Node* p = s->head, *q;while (p->level != 0) p = p->down;while (p) {q = p->next;clearNode(p);p = q;}free(s);
}void output(Skiplist* s) {Node* p = s->head;int len = 0;for (int i = 0; i < s->head->level; i++) {len += printf("%4d", i);}printf("\n");for (int i = 0; i < len; i++) printf("-");printf("\n");while (p->level > 0) p = p->down;while (p) {bool flag = (p->key != INT32_MIN && p->key != INT32_MAX);for (Node* q = p; q && flag; q = q->up) {printf("%4d", q->key);}if(flag) printf("\n");p = p->next;}
}int main() {srand(time(0));int x;Skiplist* s = getNewSkiplist(MAX_LEVEL);while (~scanf("%d", &x)) {if (x == -1)break;insert(s, x);}output(s);while (~scanf("%d", &x)) {Node* p = find(s, x);if (p) {printf("key: %d, level: %d", p->key, p->level);}else {printf("NULL\n");}}clearSkiplist(s);return 0;
}

三.哈希表与布隆过滤器

哈希表:

哈希冲突:不同元素经过哈希函数被映射到了同一个位置.

哈希冲突的解决办法:

1.开放定址法

如果发生冲突,将新的元素按照一定规则,去重新计算得出一个新的下标;

2.再哈希法

如果发生冲突,用其他的哈希函数进行计算得出新的下标;

3.建立公共溢出区法

  用另一种数据结构来存储多余的元素;

4.链式地址法(推荐)

每个下标中维护一个链表;

布隆过滤器:

传统哈希表,储存空间和元素数量强相关;

布隆过滤器,储存空间和元素数量弱相关;

若经过多个哈希函数运算,出现的结果相同,则布隆过滤器就认为此元素出现过;

注意,并不是一定出现过,而是大概率出现过;

如何减少误判:增加布隆过滤器的底层存储空间,降低重复的概率;

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>#include<iostream>using namespace std;typedef struct Node {char* s;struct Node* next;
}Node;typedef struct HashTable {Node* data;int cnt, size;
}HashTable;Node* getNewNode(const char* s) {Node* p = (Node*)malloc(sizeof(Node));p->s = _strdup(s);p->next = NULL;return p;
}HashTable* getNewHashTable(int n) {HashTable* h = (HashTable*)malloc(sizeof(HashTable));h->data = (Node*)malloc(sizeof(Node) * n);for (int i = 0; i < n; i++) {h->data[i].next = NULL;}h->size = n;h->cnt = 0;return h;
}int hash_func(const char* s) {int seed = 131, h = 0;for (int i = 0; s[i]; i++) {h = h * seed + s[i];}return h & 0x7fffffff;
}bool find(HashTable* h, const char* s) {int hcode = hash_func(s), ind = hcode % h->size;Node* p = h->data[ind].next;while (p) {if (strcmp(p->s, s) == 0)return true;p = p->next;}return false;
}void swapHashTable(HashTable* h1, HashTable* h2) {swap(h1->data, h2->data);swap(h1->cnt, h2->cnt);swap(h1->size, h2->size);return;
}void expand(HashTable* h);bool insert(HashTable* h, const char* s) {if (h->cnt >= h->size * 2) {expand(h);}int hcode = hash_func(s), ind = hcode% h->size;Node* p = getNewNode(s);p->next = h->data[ind].next;h->data[ind].next = p;h->cnt += 1;return true;
}void clearNode(Node* p) {if (p == NULL) return;if (p->s) free(p->s);free(p);return;
}void clearHashTable(HashTable* h) {if (h == NULL) return;for (int i = 0; i < h->size; i++) {Node* p = h->data[i].next, * q;while (p) {q = p->next;clearNode(p);p = q;}}free(h->data);free(h);return;
}void  expand(HashTable* h) {HashTable* new_h = getNewHashTable(h->size * 2);for (int i = 0; i < h->size; i++) {Node* p = h->data[i].next;while (p) {insert(new_h, p->s);p = p->next;}}swapHashTable(h, new_h);clearHashTable(new_h);
}
void output(HashTable* h) {printf("\n\nHash Table(%d/%d): \n", h->cnt, h->size);for (int i = 0; i < h->size; i++) {printf("%d:", i);Node* p = h->data[i].next;while (p) {printf("%s -> ", p->s);p = p->next;}printf("\n");}return;
}int main() {srand(time(0));char s[100];
#define MAX_N 2HashTable* h = getNewHashTable(MAX_N);while (~scanf("%s", s)) {if (strcmp(s, "end") == 0) break;insert(h, s);}output(h);while (~scanf("%s", s)) {printf("find(%s) = %d\n", s, find(h, s));}return 0;
}

代码练习

1. 两数之和 - 力扣（LeetCode）

哈希表做法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> h;vector<int> ret(2);for(int i = 0; i < nums.size();i++) {if(h.find(target -nums[i]) != h.end()) {ret[0] = h[target - nums[i]];ret[1] = i;break;}h[nums[i]] = i;}return ret;}
};

二分查找做法

class Solution {
public:int binary_search(vector<int>&nums, vector<int>&ind, int b, int x) {int head = b, tail = nums.size() - 1, mid;while(head <= tail) {mid = (head + tail) /2;if(nums[ind[mid]] == x) return mid;if(nums[ind[mid]] < x) head = mid + 1;else tail = mid - 1;}return -1;}vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n, 0);for(int i = 0; i < n; i++) ind[i] = i;sort(ind.begin(), ind.end(), [&](int i , int j) {return nums[i] < nums[j];});vector<int> ret(2);for(int i = 0; i < n; i++) {int j = binary_search(nums, ind, i + 1, target - nums[ind[i]]);if(j == -1) continue;ret[0] = ind[j];ret[1] = ind[i];}//if(ret[0] >ret[1]) swap(ret[0], ret[1]);return ret;}
};

35. 搜索插入位置 - 力扣（LeetCode）

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int head = 0, tail = nums.size(), mid;while(head < tail) {mid = (head + tail) /2;if(nums[mid] < target) head = mid + 1;else tail = mid;}return head;}
};

217. 存在重复元素 - 力扣（LeetCode）

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> h;for(auto x: nums) {if(h.find(x) != h.end()) return true;h.insert(x);}return false;}
};

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> h;vector<int> ret;for(auto x: nums1) h.insert(x);for(auto x: nums2) {if(h.find(x) == h.end()) continue;ret.push_back(x);h.erase(h.find(x));}return ret;}
};

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
public:bool check(string &s, int l) {int cnt[256] = {0}, k = 0;for(int i = 0; s[i]; i++) {cnt[s[i]] += 1;if(cnt[s[i]] == 1) k += 1;if(i >= l) {cnt[s[i - l]] -= 1;if(cnt[s[i - l]] == 0) k -= 1;}if (l == k) return true;}return false;;}int lengthOfLongestSubstring(string s) {int head = 1, tail = s.size(), mid;//111100000while(head < tail) {mid = (head +tail + 1) /2;if(check(s,mid)) head = mid;else tail = mid - 1;} return head;}
};

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

class Solution {
public:int findK(vector<int> &n1, int ind1, vector<int> &n2, int ind2, int k) {int n = n1.size(), m = n2.size();if(k == 1) {int a = (n1.size() == ind1 ? INT32_MAX: n1[ind1]);int b = (n2.size() == ind2 ? INT32_MAX: n2[ind2]);return min(a,b);}if(n == ind1) return n2[k - 1];if(m == ind2) return n1[k - 1];int cnt1 = min(k / 2 , n - ind1);int cnt2 = min(k - cnt1, m - ind2);cnt1 = k - cnt2;if(n1[ind1 + cnt1 - 1] <= n2[ind2 + cnt2 - 1]) {return findK(n1,ind1 + cnt1, n2, ind2, k - cnt1);}return findK(n1, ind1, n2 ,ind2 + cnt2, k - cnt2);}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();if((n + m) % 2 == 1) return findK(nums1, 0, nums2, 0, (n + m) / 2 + 1);double a = findK(nums1, 0, nums2, 0, (n + m) / 2);double b = findK(nums1, 0, nums2, 0, (n + m) / 2 + 1);return (a + b) /2.0;}
};


http://www.ppmy.cn/news/1555252.html

相关文章

从阿里云EDM到美团云：典型微服务治理平台的实战经验分享

从阿里云EDM到美团云：典型微服务治理平台的实战经验分享

目录 一. 阿里云 EDM&#xff08;Enterprise Distributed Application Service&#xff09; 二. 腾讯云 TSF&#xff08;Tencent Service Framework&#xff09; 三. 华为云 FusionStage 四. 京东云 JDC&#xff08;JD Cloud Microservice Platform&#xff09; 五. 百度智…
阅读更多...
ISP 代理提供商：互联网安全的关键参与者

ISP 代理提供商：互联网安全的关键参与者

互联网改变了我们互动、工作和开展业务的方式&#xff0c;但也带来了与安全性和可访问性相关的重大挑战。在这个数字时代&#xff0c;互联网服务提供商 (ISP) 代理提供商在解决这些问题方面发挥着关键作用。他们提供的基本服务不仅可以增强安全性&#xff0c;还可以提高用户在线…
阅读更多...
【面试题】简述rabbitmq的组织架构

【面试题】简述rabbitmq的组织架构

[面试题]简述rabbitmq的组织架构 RabbitMQ 是一种流行的消息中间件&#xff0c;其架构设计围绕消息生产者, 消息消费者和消息中转&#xff08;Broker&#xff09;展开。以下是 RabbitMQ 的主要组织架构组件和它们之间的关系&#xff1a; 1. 核心组件 1.1 Producer&#xff0…
阅读更多...
【stable diffusion部署】Stable Diffusion开源本地化的文生图图生图AI

【stable diffusion部署】Stable Diffusion开源本地化的文生图图生图AI

前言 主要功能 文生图、图生图、图像修复、处理、合成 所有的AI设计工具&#xff0c;安装包、模型和插件&#xff0c;都已经整理好了&#xff0c;&#x1f447;获取~ 系统要求 windows 10、11系统&#xff0c;建议6G显存&#xff0c;NVIDIA显卡推荐12G显存&#xff0c;内存建…
阅读更多...
Azure OpenAI 生成式人工智能白皮书

Azure OpenAI 生成式人工智能白皮书

简介 生成式 AI 成为人工智能领域新的关键词。吸纳从机器智能到机器学习、深度学习的关键技术生成式 AI更进一步&#xff0c;能够根据提示或现有数据创建新的书面、视觉和听觉内容。在此基础上大模型和大模型应用一时涌现&#xff0c;并迅速确立AI落地新范式。据 data.ai inte…
阅读更多...
AI绘画探索：通过Stable Diffusion实现角色稳定控制与线稿上色

AI绘画探索：通过Stable Diffusion实现角色稳定控制与线稿上色

在角色控制方面&#xff0c;我们都了解到midjourney的局限性&#xff0c;其无法稳定地实现目标控制。然而&#xff0c;Stable Diffusion 提供了出色的可控性&#xff0c;使我们能够有效地弥补这一缺陷。 今天就通过一个简单案例&#xff0c;给大分享如何使用 Stable Diffusion…
阅读更多...
MySQL-逻辑架构篇

MySQL-逻辑架构篇

服务器处理客户端请求 首先MySQL是典型的C/S架构&#xff0c;即Clinet/Server 架构&#xff0c;服务端程序使用的mysqld。 不论客户端进程和服务器进程是采用哪种方式进行通信&#xff0c;最后实现的效果是&#xff1a;客户端进程向服务器进程发送一段文本&#xff08;SQL语句…
阅读更多...
【069】基于51单片机WIFI智能家居【Proteus仿真+Keil程序+报告+原理图】

【069】基于51单片机WIFI智能家居【Proteus仿真+Keil程序+报告+原理图】

☆、设计硬件组成&#xff1a;51单片机最小系统WIFI模块DHT11温湿度传感器AT24C02存储芯片LCD1602液晶显示继电器按键电路蜂鸣器LED灯。 1、本设计采用STC89C51/52、AT89C51/52、AT89S51/52单片机作为主控芯片&#xff0c;ESP8266实现WIFI远程数据传输&#xff0c;随时随地在外…
阅读更多...
最新文章

Copyright @ 2022~2023