做了一题JS面试题，写的很不好，寻求更好的方法_Html5_论坛

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

qi***hu 分类：Html5 人气：3734 回帖：26 发布于6年前收藏

题目：

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

标签：html5 javascript

讨论这个帖子（26）垃圾回帖将一律封号处理……

Lv6 码匠

飞***猪交互设计师 6年前#1

提供 ES2017 的写法：

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
}

https://jsfiddle.net/hsfzxjy/...

Lv7 码师

超***媒 Web前端工程师 6年前#2

不知道哪位大神能给个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');

Lv4 码徒

醉***o JAVA开发工程师 6年前#3

var str = "cbaacfdeaebb";
var map = {};
var set = [];
str.split('').forEach(function(char, i, temp) {
    (temp=map[char])? (set[temp.index].qty+=1): set.push( map[char]=({char:char, index: set.length, qty:1}) );
});
var result = set.reduce(function(curr, next) {
    return curr.qty <= next.qty? curr: next;
});
console.log( result.char );

不依赖对象属性排序, 支持也主流, 性能不会比其他写法差

Lv6 码匠

邹***b CEO 6年前#4

你们都这么精简，我都不好意思贴了。

var str = 'cbaacfdeaebb', ranks = {};
str.split('').forEach(function (x) { ranks[x] = ranks[x] ? ranks[x] + str.length : str.length });
var arr = Object.keys(ranks).sort(function(a, b){ return ranks[a] > ranks[b] });
arr.sort(function(a, b) { return (ranks[a] + str.indexOf(a)) > (ranks[b] + str.indexOf(b)) });
console.log('char:', arr[0], ', count:', ranks[arr[0]] / str.length);

结果：char: f , count: 1

Lv6 码匠

sh***ng 交互设计师 6年前#5

最初思路就是用对象存储字符串中的字符出现的次数，然后再针对结果进行大小比对。
但是考虑到对象迭代顺序问题，只能加个数组作为字符出现顺序的排序了。

var leastTime = function(str) {
  if (!str.length) {
    return '空串';
  }
  if (str.length === 1) {
    return str;
  }
  var obj = {},
    key, arr = [],
    min, result = {};
  for (var i = 0, j = str.length; i < j; i++) {
    key = str[i];
    if (!obj[key]) {
      obj[key] = 1;
      arr.push(key);
    } else {
      obj[key] += 1;
    }
  }
  min = obj[arr[0]];
  for (var i = 1, j = arr.length; i < j; i++) {
    if (min > obj[arr[i]]) {
      min = obj[arr[i]];
      result = {};
      result[arr[i]] = min;
    }
  }
  return result;
};

测试：

leastTime('1112323');
leastTime('11aa12323');
leastTime('1a2b3c4de');

Lv3 码奴

随***吧 JS工程师 6年前#6

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

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()的方法是错的，我就删掉了。

文明上网，理性发言！ 😉 阿里云幸运券，戳我领取