2017/3/16 16:11 更新
非常感谢各位大大的回答,真的非常感动,每个答案我会一个一个看过去,正在努力学习中...
实现一个算法,寻找字符串中出现次数最少的、并且首次出现位置最前的字符。如cbaacfdeaebb
,符合要求的是f
,因为他只出现了一次(次数最少)。并且比其他只出现一次的字符(如d
)首次出现的位置最靠前。
下面是我的写法,小弟没学过数据结构与算法,半路出家,基础不好,写的太烂了,效率无比低下,希望有各位大大能够给出一些更好的写法。
var str = "cbaacfdeaebb";
var arr = str.split('');
// 各元素以及对应出现的次数
var res = arr.reduce(function (obj, key, index, arr) {
if(obj.hasOwnProperty(key)) {
obj[key] ++;
} else {
obj[key] = 1;
}
return obj;
}, {});
// 次数组成的数组
var indexArr = [];
for(var prop in res) {
indexArr.push(res[prop]);
}
// 找出出现次数最少的数
var minTimes = Math.min.apply(null,indexArr);
// 出现次数最少元素的数组
var eleArr = [];
for(var p in res) {
if(res[p] === minTimes) {
eleArr.push(p);
}
}
console.log(eleArr[0])
console.time()
function findFirstChar(string) {
const desc = [];
[...string].forEach((char, index) => {
const item = desc.find(item => item.char === char)
item ? item.count++ : desc.push({ char, index, count: 1 })
})
return desc.sort((a, b) => a.count - b.count)[0]
}
const findStr = 'cbaacfdeaebb'
const find = findFirstChar(findStr)
console.log(`在字符串[${findStr}]中, 出现次数最少的字符是: ${find.char}, 它的索引是: ${find.index}, 它出现了 ${find.count} 次`)
console.timeEnd() // default: 0.635ms
var o = [].reduce.call('cbaacfdeaebb',function(p,n){
return p[n] = (p[n] || 0) + 1,p;
},{}),
s = Object.keys(o).reduce(function(p,n){
return o[p] <= o[n] ? p : n;
});
console.log(s,o[s]); // 不知道正不正确...
// 更改 过 的 代码!!! 大神 快来 看 我 想 的 对不对
var o = [].reduce.call(window.v = 'cbaacfdeaebb',function(p,n){
return p[n] = (p[n] || 0) + 1,p;
},{}),
s = Object.keys(o).reduce(function(p,n){
// 其实 写 的 时候 我 有点 犹豫 不过 看 了 @边城 的 提示 我 想到 了 用 indexOf @小明
// 为了 弥补 缺点 不保证 Object.keys 的 顺序 所以 进行 了 更改
// 就算 对象 列表 是 无序 的 但是 字符 串 的 下标 是 有序的 所有 同等 数量 一样 的 再进 行 一次 下标 判断
if (o[p] < o[n]) return p;
if (o[p] > o[n]) return n;
return v.indexOf(p) < v.indexOf(n) ? p : n;
});
console.log(s,o[s]);
@边城 @小明
var str = "cbaacfdeaebb";
var obj = {};
var min;
var element;
for(var i = 0; i < str.length ;i++){
var k = str.charAt(i);
if(obj[k]){
obj[k]++;
}else{
obj[k] = 1;
}
}
min = obj[str.charAt(0)];
element = str.charAt(0);
for(var j in obj){
if(obj[j] < min){
min = obj[j];
element = j;
}
}
console.log("出现次数最少的是"+min+"次");
console.log("出现次数最少且最前面的元素为"+element);
//方法1
function findFirstLeastLetter(str) {
var arr = str.split('');
var letterObj = {}
arr.forEach(function (n, i) {
if(letterObj[n] == undefined) {
letterObj[n] = {length: 0, firstIndex: i, letter: n};
} else {
letterObj[n].length++;
}
});
var arr2 = [];
for(var i in letterObj) {
arr2.push(letterObj[i]);
};
arr2.sort(function (a, b) {
if(a.length == b.length) {
return a.firstIndex - b.firstIndex;
} else {
return a.length - b.length;
}
})
return arr2[0].letter;
}
var str = 'cbaacfdeaebb';
var firstLeastLetter = findFirstLeastLetter(str);
console.log(firstLeastLetter);
//方法2:
function jianCe2(str) {
var arr = str.split('');
arr.sort(function (a, b) {
var r1l = str.match(new RegExp(a, 'g')).length;
var r2l = str.match(new RegExp(b, 'g')).length;
return r1l == r2l ? str.indexOf(a) - str.indexOf(b) : r1l - r2l;
});
return arr[0];
}
console.log(jianCe2('cbaacfdeaebb'));
一楼的回答有个bug。
就是我把参数变成"cbaacffddeaebb"
时,会输出undefined(按理是输出c)。那是因为lesTimes
被赋值为1
而传的字符串里面重复字符串最少是两个,于是我把代码改成:
function leastTime(str) {
//定义一个对象,把对应字母存储到属性中,若属性已存在,则增加数量
var obj = {};
//取个超大的数作为lestTimes初始值,如果需要你可以改成无限大
var lestTimes = 1000000;
//在这个for循环中完成字母次数统计
for(var i = 0; i < str.length; i++) {
var key = str[i];
if(obj.hasOwnProperty(key)) {
//若存在,对应属性加1
obj[key]++;
} else {
//不存在则增加对应属性,并且设置出现次数为1
obj[key] = 1;
}
}
/*
*这里是我改的
*/
//result是存放最终的结果,其实这整个代码还能再写简洁点,为了好理解我就不改了
var result;
for(var key in obj) {
if(obj[key] < lestTimes) {
lestTimes=obj[key];
//当最小值被替换时,同时更新最终要返回的值
result = key;
}
}
return result;
}
var str = 'cbaacffddeaebb';
console.log(leastTime(str))
以上修改借鉴于JasonCloud同学的回答
/*这里是之前的代码,可以对比一下*/
for(var key in obj) {
if(obj[key] < lestTimes) {
lestTimes = obj[key];
}
}
//遍历生成的对象 第一次检测某个属性的值等于最小次数即可
for(var j in obj) {
if(obj[j] === lestTimes)
return j;
}
我之前的方法有很大的风险,特别是在for..in或者Object.keys()时候如果对象的简直是数字字符串时,并不能保证他的顺序;还是楼上的‘边城’大神考虑的周全在初始化counter的时候顺便吧位置给标记进去了;
function aphaCount(str){
var obj = [...str].reduce((prev,cur,idx)=>{
return prev[cur] ? prev[cur]['counter']++ : prev[cur] = {ch:cur,counter:1,index:idx},prev;
},{});
return Object.keys(obj).map((v,k)=>obj[v]).reduce((prev,cur)=>{
return cur['counter'] < prev['counter'] ? cur : cur['counter'] > prev['counter'] ? prev : cur['index'] < prev['index'] ? cur : prev;
});
}
函数里面判断类型以及空格情况就没有考虑。
function firstTime(str){
var obj_result = {},orginVaule = 0,orginKey = '';
for(let i of str){
if(obj_result[i]){
obj_result[i]++;
}else{
obj_result[i] = 1;
}
}
orginVaule = obj_result[str[0]];
orginKey = str[0];
for(let i in obj_result){
if(obj_result[i]<orginVaule){
orginVaule = obj_result[i];
orginKey = i;
}
}
return orginKey;
}