网站被k,枣阳网站建设公司,合肥大型网站建设,微信公众平台推广方案二分的概念
二分算法#xff1a;是用来在一个有序数组中查找一个元素的算法。时间复杂度O#xff08;log n#xff09;
二分的二段性
集合中的元素有存在分界线#xff0c;给定条件可以将集合中的元素分为两部分#xff0c;一部分满足条件#xff0c;一部分不满足条件…二分的概念
二分算法是用来在一个有序数组中查找一个元素的算法。时间复杂度Olog n
二分的二段性
集合中的元素有存在分界线给定条件可以将集合中的元素分为两部分一部分满足条件一部分不满足条件。不断将区间一分为二逼近端点
1.查找当前有序数组中大于等于x的第一个数取区间靠左的值 int arr[]{1,2,3,4,5};
int l0,rarr.length-1;
int x2;
while(lr){int mid(lr)/2;//取区间中间的位置靠左的值if(arr[mid]x) rmid;//区间向左缩短一半else lmid1;//区间向右缩短一半
} 2. 查找当前有序数组中小于等于x的最后一个数 int arr[]{1,2,3,4,5};
int l0,rarr.length-1;
int x2;
while(lr){int mid(lr1)/2;//取区间中间位置靠右的位置if(arr[mid]x) rmid-1;//区间向左缩短一半else lmid;//区间向右缩短一半 } 例题实战 1
问题描述
给定一个数组其采用如下代码定义 int data[200]; for(i0;i200;i){ data[i]4*i6; } 先给定某个数(data数组中)请你求出他在数组中的位置
输入描述
输入一个待查的整数该整数一定在数组data中
输出描述
输出该整数在数组中的指标
代码 package erfen;
import java.util.*;
public class erfen {public static void main(String[] args) {// TODO Auto-generated method stubScanner scannew Scanner(System.in);int resscan.nextInt();//待查数int data[]new int [200];for(int i0;i200;i) {data[i]4*i6;}int l0, r data.length-1,mid0;while(lr) {mid(lr)/2;//中间左侧if(data[mid]res) {rmid;}else {lmid1;}}System.out.print(l);}}例题实战 2
问题描述
给定n个数形成一个序列a那定义如果一个连续子序列包含序列a中所有不同元素。则该连续子序列便为蓝桥序列现在问你该蓝桥序列长度最短为多少
例如 1 2 2 2 3 2 2 1 包含3个不同的数123而3 2 2 1符合题目要求因此答案为4
连续子序列从序列a中选取若干个连续的数形成一个序列叫做连续子序列
输入格式
第一行输入一个整数n表示序列长度
第二行输入n个元素。
输出格式
输出一个整数表示最短的蓝桥序列长度。
代码 package erfen;
import java.util.*;public class erfen2 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scannew Scanner(System.in);int nscan.nextInt();int []arrnew int[n];for(int i:arr) {arr[i]scan.nextInt();}//去重操作SetInteger setnew HashSet();for(int i:arr) {set.add(arr[i]);}//计算a序列中的不同元素int mset.size();//满足条件的最小个数int l1,rarr.length;while(lr) {int mid(lr)/2;if(check(mid,arr,m)) rmid;else lmid1;}System.out.println(l);}public static boolean check(int mid, int[] arr, int m) {int narr.length;int []fnew int [1001];int l0;int r0;//同向双指针int ans0;//当前区间含有的元素个数while(rn) {f[arr[r]];if(f[arr[r]]1) {ans;}if(r-l1mid) {f[arr[l]]--;if(f[arr[l]]0){ans--;}l;}r;if(ansm) {return true;}// TODO Auto-generated method stub}return false;}
}
