javascript - Fastest way to get ONLY unique values from array? - Stack Overflow

admin管理员组

文章数量:1236724

I have an array like this

students = [{name: 'Abbey', age: 25}, {name: 'Brian', age: 45},
            {name: 'Colin', age: 25}, {name: 'Dan', age: 78}]

and I want the output to be;

uniqueAges = [45, 78]

To be clear, if there is an age value that appears more than once in the students array, I do not want any of the objects with that age in my uniqueAges array. 'Abbey' and 'Colin' have the same age so they are both out.

I know I can do something like this and run uniqueAgeGetter(students)

   function uniqueAgeGetter(list){
   var listCopy = list.slice();
   var uniqueAges = list.slice();
   for (var i = list.length - 1; i >= 0; i--) {
        for (var j = listCopy.length - 1; j >= 0; j--) {
            if(listCopy[j].name !== list[i].name && 
                listCopy[j].age == list[i].age){
                  uniqueAges.splice(i, 1)
                }   
            }
    }
   console.log(uniqueAges)
   return uniqueAges
 }

But is it possible to do it without a second loop? I'm not an expert on time plexity but I am trying to find if it is possible this task can be O(n).

Edit: I am not asking if uniqueAgeGetter be rewritten to read nicer or use functions like map, reduce or filter (as my understanding is they are ultimately a loop as well).

My question is can uniqueAgeGetter be refactored in a way that reduces the time plexity? Can it be done with only one loop?

Thank you.

I have an array like this

students = [{name: 'Abbey', age: 25}, {name: 'Brian', age: 45},
            {name: 'Colin', age: 25}, {name: 'Dan', age: 78}]

and I want the output to be;

uniqueAges = [45, 78]

To be clear, if there is an age value that appears more than once in the students array, I do not want any of the objects with that age in my uniqueAges array. 'Abbey' and 'Colin' have the same age so they are both out.

I know I can do something like this and run uniqueAgeGetter(students)

   function uniqueAgeGetter(list){
   var listCopy = list.slice();
   var uniqueAges = list.slice();
   for (var i = list.length - 1; i >= 0; i--) {
        for (var j = listCopy.length - 1; j >= 0; j--) {
            if(listCopy[j].name !== list[i].name && 
                listCopy[j].age == list[i].age){
                  uniqueAges.splice(i, 1)
                }   
            }
    }
   console.log(uniqueAges)
   return uniqueAges
 }

But is it possible to do it without a second loop? I'm not an expert on time plexity but I am trying to find if it is possible this task can be O(n).

Edit: I am not asking if uniqueAgeGetter be rewritten to read nicer or use functions like map, reduce or filter (as my understanding is they are ultimately a loop as well).

My question is can uniqueAgeGetter be refactored in a way that reduces the time plexity? Can it be done with only one loop?

Thank you.

• javascript
• node.js
• algorithm
• time-plexity

Share Improve this question Follow edited Mar 14, 2018 at 4:17 FatihAkici 5,10933 gold badges3333 silver badges5050 bronze badges asked Mar 14, 2018 at 3:46 damtypodamtypo 16011 silver badge2020 bronze badges 4

• 1 Try to use Set – oybek Commented Mar 14, 2018 at 5:47
• @oybek Set is great, but it is not widely supported yet – Victor Commented Mar 17, 2018 at 21:45
• As has been shown, O(n) plexity is quite possible. But getting an output of a well-formed array [45, 78] is not possible in a single iteration over all elements. (All the solutions here require more than one iteration over multiple elements) However, it would be possible to get the desired output in a Set while iterating over elements only once. Is that something you're interested in? – CertainPerformance Commented Aug 18, 2019 at 10:59
• 1 @Victor The vast majority of browsers support Sets. They're an ES2015 feature, and for the most part, only the very obsolete browsers which do not get updated do not understand Sets. – CertainPerformance Commented Aug 18, 2019 at 11:01

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 6

This can be done in O(n) time by counting the number of times an age has been seen, and filtering out the ages with a count more than one.

Since ages have reasonable limits, we can use an integer array of length equal to the maximum possible age to store the age counts. In the example below, I take the maximum possible age to be a fortable 200.

var students = [
  {name: 'Abbey', age: 25 }, 
  {name: 'Brian', age: 45 },
  {name: 'Colin', age: 25 }, 
  {name: 'Dan', age: 78 }
];

var studentAges = students.map(val => val.age);
var ageCounts = Array(200).fill(0);

studentAges.forEach(age => ageCounts[age] += 1);

var uniqueAges = studentAges.filter(age => ageCounts[age] == 1);

console.log(uniqueAges);

• The first idea, we can do over two step:

  Step1: Sort the array

  -- There are many algorithms to do it. As I know, currently, the plexity of best algorithm now is O(Nlog(N)) with N is the number of array.

  Step2: Remove the duplicated elements

  -- The plexity of this step is O(N) So, over two steps, the plexity is O(N) + O(Nlog(N)). Finally, the plexity is O(Nlog(N))

• The second idea

  This also has the plexity is O(Nlog(N)) but it will be O(N) for next time you want to get the unique age.

  Instead of saving the data in array, you can rebuild in a binary search tree with a little custom. This node in this tree will save all the elements with same age.

  The plexity for the first time you build the tree is O(Nlog(N))

About the algorithm which has the plexity is O(N), currently, I think there are no technique to solve it. :D

You can use reduce

The first reduce is to summarise the array and convert it into an object using the age as a the key. Using the age as the key will make it easier to check if the age already exist. The object properties will have an array value like [2,true], where the first element is the age and the second element tells if the age has duplicates. Using Object.values will convert the object into an array.

The second reduce is to form the desired output.

let students = [{name: 'Abbey', age: 25 }, {name: 'Brian', age: 45 },{name: 'Colin', age: 25 }, {name: 'Dan', age: 78 }];

let uniqueAges = Object.values(students.reduce((c, v) => {
  if (c[v.age] === undefined) c[v.age] = [v.age, true];
  else c[v.age][1] = false;
  return c;
}, {})).reduce((c, v) => {
  if (v[1]) c.push(v[0]);
  return c;
}, []);

console.log(uniqueAges);

Here is one way you could do it. I think the time plexity would be O(n^2) where n is the number of elements in the original array and m is the number of unique elements in the output array.

const students = [
  {name: 'Abbey', age: 25 }, 
  {name: 'Brian', age: 45 },
  {name: 'Colin', age: 25 }, 
  {name: 'Dan', age: 78 }
];

const uniqueStudents = students.map(val => val.age)
  .sort()
  .reduce((current, next) => {
    return current.length === 0 ? [].concat(current, next)
      : current[current.length - 1] !== next ? [].concat(current, next)
        : current.slice(0, -1);
  }, []);
  
console.log(uniqueStudents);

for getting unique elements

const data = [128, 128,128,121,127,127,121,121,121,121,122,125];
const uniqueData = Object.keys(data.reduce((r,c) => {r[c] = true; return r;}, {}))
console.log(uniqueData)

But doing this will sort the array and will not keep the original order of the array

Complexity O(n)

The fastest way with a single iteration.

const students = [
  {name: `Abbey`, age: 25}, 
  {name: `Brian`, age: 45},
  {name: `Colin`, age: 25}, 
  {name: `Dan`, age: 78},
  {name: `Dan`, age: 25}
]

// no global variables
function unique(key) {
  const occurrences = {}
  const list = {}
  return (result, next, index, {length}) => {
    const value = next[key]
    if (list[value]) {
      occurrences[value] = value
    }
    else {
      list[value] = value
      result.push(value)
    }
    return index === length - 1 ? result.filter(v => !occurrences[v]) : result
  }
}

const uniqueNames = students.reduce(unique(`name`), [])
const uniqueAges = students.reduce(unique(`age`), [])

console.log(uniqueAges)

本文标签： javascriptFastest way to get ONLY unique values from arrayStack Overflow