javascript - 做了一题JS面试题，写的很不好，寻求更好的方法

Question

题目：

---

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])

Answer 1

斗胆来评价一下诸位大神的答案。。。

@莲_涳栢__ :

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]); 

正统的Hash Table思路。缺点是Object.keys()不能保证顺序，所以存在风险。

---

@边城 :

const all = "cbaacfdeaebb".split("")
    .reduce((all, ch, i) => {
        const m = all[ch] || (all[ch] = { ch: ch, index: i, count: 0 });
        m.count++;
        return all;
    }, {});

const theOne = Object.keys(all)
    .map(ch => all[ch])
    .reduce((min, t) => min.count === t.count
        ? (min.index > t.index ? t : min)
        : (min.count > t.count ? t : min));

console.log(`${theOne.ch}: ${theOne.count}`);

引入了index来解决顺序问题，比较健康和简练。

---

@u3u

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]
}

利用数组代替Hash Table，解决了顺序问题，思路不错。
但是Array.sort()并不一定是stable的，这个造成的风险更大。

---

@hsfzxjy

const less = (x, y) => x.count <= y.count && x.first < y.first

function firstSingle (string) {
  let map = {}
  string.split('')
    .forEach((char, index) => {
      if (map[char]) 
        map[char].count++
      else
        map[char] = { count: 1, first: index, char }
    })
  return Object.values(map).reduce((x, y) => less(x, y) ? x : y).char
}

思路相似，利用Hash Table，并引入了index解决顺序问题。
ES2017还没有正式发布，Object.values目前还是草案。
另外原谅我强迫症重新排个版：

const less = (x, y) => (x.count <= y.count && x.first < y.first) ? x : y;

function firstSingle (string) {
  let map = {}
  string.split('')
        .forEach((char, index) => {
            map[char] ? map[char].count++ : map[char] = { count: 1, first: index, char } 
        });
  return Object.values(map).reduce(less).char
}

---

最后是我的two cents:

var str = "cbaacfdeaebb";

var result = [...new Set(str)]
            .map(el => ({el, len: str.split(el).length}))
            .reduce((a,e) => (a.len > e.len ? e : a))
            .el;

Answer 2

感谢夜店小新新指出另一个问题：for-in输入的时候，如果属性为纯数字，那么输出顺序不会按照创建属性的顺序，比如字符串为'2211'，输出会先输出属性1，根据这个情况，增加一个数组保证输出的顺序，更正后代码如下，如果还有问题欢迎指出：

function leastTime(str) {
      //定义一个对象，把对应字母存储到属性中，若属性已存在，则增加数量
      var obj = {};
      
      /*更正部分*/
      //增加一个数组记录生成属性的顺序
      var arr = [];
      /*更正部分结束*/
      
      //取个超大的数作为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;
           /*更正部分*/
          //在数组中记录下新增属性
          arr.push(key)
          /*更正部分结束*/
        }

      }
     
      //第一次遍历生成的对象 求出leastTime的结果
      for (var j in obj) {
        if (obj[j] < lestTimes)
          lestTimes = obj[j];
      }
      console.log(arr)
     
      //第二次遍历生成的对象 第一次检测某个属性的值等于最小次数即可
      /*更正部分*/
      //第二次遍历的时候不用for-in 而是按照数组存储的顺序 这样就可以解决for-in带来的不确定性
      for (var j = 0; j < arr.length; j++) {
        var key = arr[j];
        if (obj[key] === lestTimes)
          return key;
      }
       /*更正部分结束*/
    }
    var str = '2211';
    console.log(leastTime(str))

---

答案再次更新的分割线

---

感谢JayZangwill指出错误，更正一下之前的问题，在第一次for循环存储字母的时候，不应该更新leastTime的值，因为例如abab这种字符串可能导致leastTime的值，在第一次碰到a被更新成1，实际上a和b都是2个，导致最后结果不准确，所以把求leastTime的步骤放在字符串存储之后，更正后代码如下：

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;
      }
     
    }
    /*--更正部分开始--*/
    //第一次遍历生成的对象 求出leastTime的结果
    for (var j in obj) {
      if (obj[j] < lestTimes)
        lestTimes = obj[j];
    }
    /*--更正部分结束--*/
    //第二次遍历生成的对象 第一次检测某个属性的值等于最小次数即可
    for (var j in obj) {
      if (obj[j] === lestTimes)
        return j;
    }
  }
  var str = 'cbaacfdeaebb';
  console.log(leastTime(str))

---

答案更新的分割线，以下是原答案

---

最最近刚好复习了一些js的基础，这种题其实和数组去重之类的很相似，先上代码：

 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;
      }
      //存储的同时顺便更新最小出现的次数
      if (obj[key] < lestTimes)
        lestTimes = obj[key];
    }
    //遍历生成的对象 第一次检测某个属性的值等于最小次数即可
    for (var j in obj) {
      if (obj[j] === lestTimes)
        return j;
    }
  }
  var str = 'cbaacfdeaebb';
  console.log(leastTime(str))

在注释里面写的比较清楚了，不过还是讲一下思路：

• 首先对输入的字符串遍历一次，用一个对象的属性来存储这些字符串出现的次数。同时在循环的过程中，让leastTime这个变量始终保存着出现次数最少的那个值。

• 对生成的对象，检测每个属性对象的值（就是每个字母出现的次数），第一次检测到等于leastTime，就是出现次数最少并且第一次的

补充一下，这种算法的好处是计算速度快，时间复杂度基本是最低的，因为用的是数据散列的思路，缺点是开的空间比较大，因为对于每个不同的字母都增加一个对应的属性。至于时间和空间如何取舍就看题主自己了，不过这道题本身空间复杂度大不到那哪里去，因为最多26个字母最多加上数字，所以这种算法我认为基本上是完美符合你的意思。如果满意清采纳~如果想看更多前端方面的基础，欢迎关注我的专栏~

Answer 3

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]);

@边城 @小明

Answer 4

其实很好理解的, 
缩减一些代码量也是可以的.

其次我想说一下, 有很多不运行自测就发上来的错误答案. 呵呵哒

更新版本(加注释):

var str = "aaasdsrhksaoashgas";
function findMinLetter(str){
  if(!!!str && typeof(str) !== "string")return; //如果是空串或者非字符串返回
  var arr = [], letter = str.split("")[0], count = 0;//arr 目标数组 内容为letter: 字母, count: 字母存在的个数, letter第一个字母(初始值), count 个数(初始值0)
  
  while(str.indexOf(letter) > -1){//循环如果str中含有letter, 执行以下代码, 首次肯定会往下执行
    count ++;//count++
    str = str.replace(letter, "");//从str中删除当前letter并重新赋值给str, 从前往后
    if(str.indexOf(letter) < 0){//再次判断是否含有letter 如果没有执行以下代码
      arr.push({letter: letter, count: count});//往arr中push当前letter的字母和个数
      letter = str.split("")[0];//letter重新赋值为字符串的第一个字母
      count = 0;//同时count重置为0
    }
  }
  //返回一个立即执行函数 获取arr中count最少的且最先出现的字母, 输出为字符串
  return (function (arr){
    var letter = "", count = 0;
    arr.forEach(function(o, i){
      if(!!!letter || count > o.count){//这里判断 如果letter不存在(即为第一次, 非第一次均为false) 或 count > 当前循环的o.count时, 相等时也不会进入函数域赋值, 所以一定会循环到一个最少且最先出现的值
        letter = o.letter;
        count = o.count;
      }
    });
    return "最少且最靠前的字符为: " + letter + ", 出现次数为: " + count;
  })(arr);
}
findMinLetter(str);

总结: 简单易懂, 且比较完善

更新, 函数第一行判断增加 `!` !== "string", 之前是代码错误少了!
感谢 @一只会飞的猪[liutong] 提醒

Answer 5

我也写一段玩玩：

const all = "cbaacfdeaebb".split("")
    .reduce((all, ch, i) => {
        const m = all[ch] || (all[ch] = { ch: ch, index: i, count: 0 });
        m.count++;
        return all;
    }, {});

const theOne = Object.keys(all)
    .map(ch => all[ch])
    .reduce((min, t) => min.count === t.count
        ? (min.index > t.index ? t : min)
        : (min.count > t.count ? t : min));

console.log(`${theOne.ch}: ${theOne.count}`);
// 输出 f: 1

我不确定 {} 在用 Object.keys 遍历的时候，键是不是加入的顺序，所以加上了对 index 的判断。如果可以保证 keys 是按加入序的，那 @莲_涳栢__ 的应该是最简洁的。

Answer 6

不知道哪位大神能给个o(n)的？

function findFirstSingle(str){
    var obj = {}, array = [], index = 0;
    for(var i = 0, len = str.length ; i < len ; i ++){
        var v = str[i];
        if(obj[v] === undefined){
            array.push(v);
            obj[v] = index ++;
        }else{
            var j = obj[v];
            while(j >= 0){
                if(v == array[j])
                    break;
                j --;
            }
            if(j < 0)continue;
            array.splice(j,1);
            index --;
        }        
    }
    return array[0];
}
findFirstSingle('cbaacfdeaebb');

Answer 7

你的代码已经很有灵性了，我想半天没有更好的办法了。

Answer 8

只是写着玩玩，没有测。。。

function least(str){
    var map = {};
    return  [].reduce.call(str, (prev, ele)=>{
                      if(map.hasOwnProperty(ele)) {
                            prev[map[ele]].counter++;
                        } else {
                            map[ele] = prev.length;
                            prev.push({ ele, counter: 1 });
                        }
                        return prev;
                    },[])
                 .reduce((prev, ele)=>prev.counter <= ele.counter ? prev : ele)
                 .ele;
}

感谢@小明提醒，之前charCodeAt()的方法是错的，我就删掉了。

Answer 9

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

Answer 10

一楼的回答有个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;
}