vue项目接口域名动态的获取方法
216
2023-06-03
Java数据结构之查找
前言:查找是开发中用的非常多的一项,比如mysql中的查找,下面主要简单介绍一下查找。
1:线性表查找
线性表查找主要分为顺序查找和链式查找,顺序表查找都是从一端到另一端进行遍历。比如下面代码
public int indexOf(T x){
if (x!=null){
for (int i=0;i if (this.element[i].equals(x)){ return i; } } } return -1; } public T search(T key) { return indexOf(key)==-1?null:(T) this.element[indexOf(key)]; } 第二种是链式查找也非常简单 public T search(T key) { if (key==null){ return null; } Node while (p!=null){ if (p.data.equals(key)){ return p.data; } p=p.next; } return null; } 2:基于有序顺序表的二分查找 这个用的比较多,因为查询效率比较高,但是有限制条件,1是顺序存储,2必须有序,所以每次只需要和中间值进行比对,如果大于中间值,说明在key值在后面,如果小于中间值,说明key在前面。 pvPyszZAPublic static if (key != null) { while (begin <= end) { int mid = (begin + end) / 2; if (values[mid].compareTo(key) == 0) { return mid; } if (values[mid].compareTo(key) < 0) { begin = mid + 1; } if (values[mid].compareTo(key) > 0) { end = mid - 1; } } } return -1; } public static int binarySearch(int[] arrays, int key) { if (arrays == null || arrays.length == 0) { return -1; } int start=0,end=arrays.length-1; while (start <=end) { int mid = (start + end) / 2; if (arrays[mid] == key) { return mid; } if (arrays[mid] < key) { start = mid + 1; } if (arrays[mid] > key) { end = mid - 1; } } return -1; } 3:分块索引查找 我们都知道查字典,首先要查询是字的拼音,然后定位到字页数的一个位置,比如查找张这个字,我们先查询z,然后看哪些页是z,然后在这一块进行查找。ok我们做个简单的例子 现在我们已知一个数组里面存放的是java的关键字,那么我们给出一个关键字来判断是否在这个数组中。首先我们看下关键字的数组 private static String[] keyWords={"abstract","assert","boolean","break","byte","case", "catch","char","continue","default","do","double","else","extend","false","final", "finally","float","for","if","implements","import","instaceof","in","interface", "long","native","new","null","package","private","protectd","public","return","short", "static","super","switch","synchronized","this","throw","transient","true","try","void","volatile","while"}; 然后我们思考一下建立索引,因为英文单词是26个字母组成,那么我们效仿字典,把26个字母存起来,然后记录每个字母的位置。 private static class IndexItem implements Comparable String frist; int start; public IndexItem(String frist,int start){ this.frist=frist; this.start=start; } 其中frist是字母,二start是字母的索引,比如abstract是a0,那么assert就是a1了以此类推 public int compareTo(IndexItem o) { return this.frist.compareTo(o.frist); } private static IndexItem[] index;索引表 static { index = new IndexItem[26]; int i = 0, j = 0, size = 0; for (i = 0; j < keyWords.length && i < index.length; i++) { char ch = keyWords[j].charAt(0); IndexItem item = new IndexItem(ch + "", j); if (item != null) { index[i] = item; size++; } j++; while (j < keyWords.length && keyWords[j].charAt(0) == ch) { j++; } } int oldCount = index.length;利用trimTosize方法对数组进行压缩 if (size < oldCount) {http:// IndexItem[] items = index; index = new IndexItem[size]; for (int m = 0; m < size; m++) { index[m] = items[m]; } } } 我们创建一个静态块,在类被加载的时候运行。最后我们利用2次2分查找第一找到索引,然后通过索引匹配到值 public static boolean isKeyWord(String str){ IndexItem indexItem=new IndexItem(str.substring(0,1),-1); int pos=BSArry.binarySearch(index,indexItem); int begin=index[pos].start; int end; if (pos==index.length-1){ end=keyWords.length-1; }else { end=index[pos+1].start-1; } return BSArry.binarySearch(keyWords,begin,end,str)>=0; } 4:散列表的查找 散列的查找非常高效,但是我们必须要完成2项工作,一个是散列函数,另一个是解决冲突。下面看一下如何利用单链表简单的实现hash。 public class HashSet private SingleLinkedList public HashSet(int size) { this.table = new SingleLinkedList[Math.abs(size)]; for (int i = 0; i < table.length; i++) { table[i] = new SingleLinkedList } } public HashSet() { this(97); } private int hash(T x) {//利用hashCode解决 int key = Math.abs(x.hashCode()); return key % table.length; } public void insert(T x) { this.table[hash(x)].insert(0, x); } public void remove(T x) { this.table[hash(x)].remove(x); } public T search(T key) { return table[hash(key)].search(key); } }
if (this.element[i].equals(x)){
return i;
}
}
}
return -1;
}
public T search(T key) {
return indexOf(key)==-1?null:(T) this.element[indexOf(key)];
}
第二种是链式查找也非常简单
public T search(T key) {
if (key==null){
return null;
}
Node
while (p!=null){
if (p.data.equals(key)){
return p.data;
}
p=p.next;
}
return null;
}
2:基于有序顺序表的二分查找
这个用的比较多,因为查询效率比较高,但是有限制条件,1是顺序存储,2必须有序,所以每次只需要和中间值进行比对,如果大于中间值,说明在key值在后面,如果小于中间值,说明key在前面。
pvPyszZAPublic static
if (key != null) {
while (begin <= end) {
int mid = (begin + end) / 2;
if (values[mid].compareTo(key) == 0) {
return mid;
}
if (values[mid].compareTo(key) < 0) {
begin = mid + 1;
}
if (values[mid].compareTo(key) > 0) {
end = mid - 1;
}
}
}
return -1;
}
public static int binarySearch(int[] arrays, int key) {
if (arrays == null || arrays.length == 0) {
return -1;
}
int start=0,end=arrays.length-1;
while (start <=end) {
int mid = (start + end) / 2;
if (arrays[mid] == key) {
return mid;
}
if (arrays[mid] < key) {
start = mid + 1;
}
if (arrays[mid] > key) {
end = mid - 1;
}
}
return -1;
}
3:分块索引查找
我们都知道查字典,首先要查询是字的拼音,然后定位到字页数的一个位置,比如查找张这个字,我们先查询z,然后看哪些页是z,然后在这一块进行查找。ok我们做个简单的例子
现在我们已知一个数组里面存放的是java的关键字,那么我们给出一个关键字来判断是否在这个数组中。首先我们看下关键字的数组
private static String[] keyWords={"abstract","assert","boolean","break","byte","case",
"catch","char","continue","default","do","double","else","extend","false","final",
"finally","float","for","if","implements","import","instaceof","in","interface",
"long","native","new","null","package","private","protectd","public","return","short",
"static","super","switch","synchronized","this","throw","transient","true","try","void","volatile","while"};
然后我们思考一下建立索引,因为英文单词是26个字母组成,那么我们效仿字典,把26个字母存起来,然后记录每个字母的位置。
private static class IndexItem implements Comparable
String frist;
int start;
public IndexItem(String frist,int start){
this.frist=frist;
this.start=start;
}
其中frist是字母,二start是字母的索引,比如abstract是a0,那么assert就是a1了以此类推
public int compareTo(IndexItem o) {
return this.frist.compareTo(o.frist);
}
private static IndexItem[] index;索引表
static {
index = new IndexItem[26];
int i = 0, j = 0, size = 0;
for (i = 0; j < keyWords.length && i < index.length; i++) {
char ch = keyWords[j].charAt(0);
IndexItem item = new IndexItem(ch + "", j);
if (item != null) {
index[i] = item;
size++;
}
j++;
while (j < keyWords.length && keyWords[j].charAt(0) == ch) {
j++;
}
}
int oldCount = index.length;利用trimTosize方法对数组进行压缩
if (size < oldCount) {http://
IndexItem[] items = index;
index = new IndexItem[size];
for (int m = 0; m < size; m++) {
index[m] = items[m];
}
}
}
我们创建一个静态块,在类被加载的时候运行。最后我们利用2次2分查找第一找到索引,然后通过索引匹配到值
public static boolean isKeyWord(String str){
IndexItem indexItem=new IndexItem(str.substring(0,1),-1);
int pos=BSArry.binarySearch(index,indexItem);
int begin=index[pos].start;
int end;
if (pos==index.length-1){
end=keyWords.length-1;
}else {
end=index[pos+1].start-1;
}
return BSArry.binarySearch(keyWords,begin,end,str)>=0;
}
4:散列表的查找
散列的查找非常高效,但是我们必须要完成2项工作,一个是散列函数,另一个是解决冲突。下面看一下如何利用单链表简单的实现hash。
public class HashSet
private SingleLinkedList
public HashSet(int size) {
this.table = new SingleLinkedList[Math.abs(size)];
for (int i = 0; i < table.length; i++) {
table[i] = new SingleLinkedList
}
}
public HashSet() {
this(97);
}
private int hash(T x) {//利用hashCode解决
int key = Math.abs(x.hashCode());
return key % table.length;
}
public void insert(T x) {
this.table[hash(x)].insert(0, x);
}
public void remove(T x) {
this.table[hash(x)].remove(x);
}
public T search(T key) {
return table[hash(key)].search(key);
}
}
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~