(算法)只出现一次的最小数
算法 出现 一次 最小
2023-09-14 09:00:35 时间
题目:
给定一数组,里面的数字为1~N,每个数出现一次或两次,求只出现一次的最小数。
要求:
空间复杂度:O(1),时间复杂度:O(n)
思路:
题目给定的数字为1~N,因此可以通过交换的方法,将数组下标与数字对应存放,如数字1与下标为0的数字交换,数字3与下标为2的数字交换。
下面给出两种不同的交换思路:
1、假设每个数都出现两次,那么1存放的位置应该为0,1;2存放的位置应该为2,3;N存放的位置应该为2*(N-1),2*(N-1)+1.
如果出现2*(N-1),2*(N-1)+1大于数组长度,即可忽略,继续往前遍历交换。
这样交换完了之后,就会出现112233445x667788...这样的数组,再从头遍历一遍即可找出只出现一次的最小数。
2、对交换的数字做标记,例如某个位置i被标识为-1,即标识数字i+1出现了1次,某个位置i被标识为-2,即标识数字i+1出现了2次。
这样交换和标识完了之后,就会出现-2-2-1-2-1-2-1...这样的数组,再从头遍历一遍即可找出只出现一次的最小数。
代码:
#include<iostream> #include<limits.h> using namespace std; void swap(int &a,int &b){ int tmp=a; a=b; b=tmp; } int getMiniAppearOnce(int *A,int n){ int i=0; while(i<n){ int num=A[i]-1; if((2*num>=n) || (2*num+1>=n) || (i==2*num) ){ ++i; continue; } if(i==2*num+1 && A[2*num]==A[2*num+1]){ ++i; continue; } if(A[2*num]==A[i]){ swap(A[2*num+1],A[i]); } else swap(A[2*num],A[i]); } for(int i=0;i<n;i=i+2){ if(A[i]!=A[i+1]) return A[i]; } return -1; } int getMiniAppearOnce_1(int *A,int n){ int i=0; while(i<n){ if(A[i]==-1 || A[i]==-2 || A[i]==0 || A[A[i]-1]==-2){ ++i; continue; } if(i<n-1 && i+1==A[i]){ A[i+1]=-1; ++i; continue; } if(A[A[i]-1]==-1){ A[A[i]-1]=-2; // A[i]=0; ++i; continue; } else{ // if(A[A[i]-1]!=0){ int idx=A[i]-1; A[i]=A[idx]; A[idx]=-1; // } // else{ // A[A[i]-1]=-1; // ++i; // } } } for(int i=0;i<n;i++){ if(A[i]==-1) return i+1; } } int main(){ int A[]={5,3,5,2,4,3,1,1}; int n=sizeof(A)/sizeof(A[0]); cout<< getMiniAppearOnce(A,n) <<endl; int B[]={5,3,5,2,4,3,1,1}; cout<< getMiniAppearOnce_1(B,n) <<endl; return 0; }
相关文章
- Java实现蓝桥杯VIP算法训练 最大获利
- Java实现 蓝桥杯VIP 算法提高 特殊的质数肋骨
- Java实现 蓝桥杯VIP 算法训练 统计单词个数
- Java实现 蓝桥杯VIP 算法训练 完数
- Java实现 蓝桥杯 算法训练 出现次数最多的整数
- Java实现 蓝桥杯 算法训练 出现次数最多的整数
- Java实现 蓝桥杯 算法训练 出现次数最多的整数
- 【python cookbook】【数据结构与算法】12.找出序列中出现次数最多的元素
- 【python cookbook】【数据结构与算法】1将序列分解为单独的变量
- 算法练习之验证回文串,只出现一次的数字
- 算法 数组中出现次数最多的数字 MD
- (回溯法)和为n的所有不增正整数和式分解算法
- 【python cookbook】【数据结构与算法】12.找出序列中出现次数最多的元素
- 程序员的算法趣题Q56: 鬼脚图中的横线(思路1)
- 程序员的算法趣题Q14: 国名接龙
- 基于优化自适应微分电导算法的最大功率点跟踪改进最大功率点跟踪技术(Matlab代码实现)
- m基于CNN卷积网络和GEI步态能量图的步态识别算法MATLAB仿真,测试样本采用现实拍摄的场景进行测试,带GUI界面
- 智能优化算法:麻雀搜索算法-附代码
- Python实现DE差分进化算法优化支持向量机分类模型(SVC算法)项目实战
- OpenCV .直方图均衡 CLAHE算法学习
- 算法--数组中出现一次的数,其余都出现N次
- 每日算法之旅(第一天):枚举算法的平凡与伟大
- 机器学习的算法选择
- count算法计算容器中元素出现次数