js,如何找到文本中各行相同的数据
一个文本里有N条数据(一行一条),把各行字符相同(长度相同,顺序可以不同)的全部找出,比如def123,123def,d123fe.
另外:能用几种方法判断出两个字符是相同的(比如排序)
引导人民的哲学
9 years, 9 months ago
Answers
方法1,最直接的就是楼上的将字符串排序,
str.split("").sort().join("");
方法2, 比较累的方法:
将str1中char逐个核实,看是否在str2中。
str1和str2长度不等显然不是相同的,
但"abcdd"和"aabcd"也容易被误判为相同,因此还要判断都要相同个数的"a"字符才行。
一个小技巧:
在对比"a"字符时候,把str1,str2中的"a"都del删除后字符串长度仍旧相同,说明a字符个数也相同,进而才能判断。
javascript
compareStr=function(str1,str2){ var isEq=-1; if(str1.length == str2.length){ for ( k in str1){ var ele=str1[k]; var re=new RegExp(String(ele),"g") var len1=str1.replace(re,"").length ; var len2=str2.replace(re,"").length ; if(str2.indexOf(ele) == -1){ isEq = -1;break; }else if(len1 !== len2){ isEq = -1;break; }else{ return isEq=1; } } }else{ return isEq=-1; } return isEq; }
测试:
其他方法后面有空再添加。
方法3:根据数字映射为素数,累乘后数字相等,则这两个字符串不限位相等(注:有溢出危险)
compareStr2=function(str1,str2){
var res=0;
var ss=[2, 3, 5, 7, 11, 13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157];
var dic=" 0123456789abcdefghijklmnopqrstuvwxyz";
getMul=function(str_){
var mul = 1;
for(var i in str_){
var get=ss[dic.indexOf(str_[i])]
mul*=get
}
return mul;
}
Math.abs(getMul(str1)/getMul(str2)-1) < 1e-8 ? res=1 : res=-1;
return res;
}
方法4:根据数字映射为2^n,字符串长度相等,且累加后数字相等,则这两个字符串不限位相等(注:有溢出危险)
compareStr3=function(str1,str2){
var res=0;
var dic=" 0123456789abcdefghijklmnopqrstuvwxyz";
getAdd=function(str_){
var add = 0;
for(var i in str_){
var get=Math.pow(2,dic.indexOf(str_[i])+1)
add+=get
}
return add;
}
if (str1.length==str2.length){
getAdd(str1)-getAdd(str2)===0 ? res=1 : res=-1;
}else{res = -1 }
return res;
}
张是张柏芝的芝
answered 9 years, 9 months ago
应该可以不用排序,用空间换时间,减小时间复杂度。
我的想法是:
1. 用一个数组charCount统计每行中每个字符的次数,charCount中的每个元素也是一个数组,共有1 + 10 + 26 + 26个元素,第一个元素为行号,后面的其他元素分别对应0-9,a-z,A-Z中每个字符出现的次数(注意这里顺序很重要)
2. 一行一行的读取文本,记录每行中每个字符出现的次数,填充charCount
3. 遍历charCount, 从每个元素的第二项开始比较,相同的元素归为一类,不相同的元素归为一类,
4. 从3中相同的元素集合中,重复3的步骤,并且比较下一个字符,依次类推,可以确定文本中所有字符相同的行和不同的行。
这样做比利用排序快得多。
(简单的排序方法是,对每一行排序,然后对整个文本按每一行排序,然后再遍历一次,即可找到所有相同的字符串和不同的字符串)
向日葵瓜子
answered 9 years, 9 months ago