javascript - sorting array of (1,2,3) numbers in O(n) time - Stack Overflow

admin管理员组

文章数量:1344223

Given a list of numbers with only 3 unique numbers(1, 2, 3), sort the list in O(n) time. Plus sort the array using constant space O(1).

Example:

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

Here the solution i made (is no O(1) space and have empty spaces spaces in the array..): What does this function is simple .. increases the size of the arrangement to double in the case that all its elements are 2; Then it goes to its previous length (current/2) to sort its elements .. if it is 1 it does nothing, if it finds a 2 it puts it in the previous maximum length + 1, it increases the variable len and eliminates the element and if it is 3 push and delete the element .. then you have empty spaces in the array and you don't meet the plus of the problem but it's O(n).

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))

Given a list of numbers with only 3 unique numbers(1, 2, 3), sort the list in O(n) time. Plus sort the array using constant space O(1).

Example:

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

Here the solution i made (is no O(1) space and have empty spaces spaces in the array..): What does this function is simple .. increases the size of the arrangement to double in the case that all its elements are 2; Then it goes to its previous length (current/2) to sort its elements .. if it is 1 it does nothing, if it finds a 2 it puts it in the previous maximum length + 1, it increases the variable len and eliminates the element and if it is 3 push and delete the element .. then you have empty spaces in the array and you don't meet the plus of the problem but it's O(n).

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))

• javascript
• algorithm
• sorting
• big-o

Share Improve this question Follow edited Oct 29, 2019 at 8:13 RazerJs asked Oct 28, 2019 at 13:35 RazerJsRazerJs 18822 silver badges1212 bronze badges 6

• 1 Move ones to the left. In the next pass, move 3s to the right. O(n) time, O(1) space. Don't delete anything. – nice_dev Commented Oct 28, 2019 at 13:39
• 2 Possible duplicate of Is there an O(n) integer sorting algorithm? – Liam Commented Oct 28, 2019 at 13:40
• 2 @Liam Not really a duplicate since this isn't about a general-purpose sort. – John Coleman Commented Oct 28, 2019 at 13:42
• 4 en.wikipedia/wiki/Dutch_national_flag_problem – MBo Commented Oct 28, 2019 at 13:49
• Also, Dutch National Flag Problem Running in O(n) and lots and lots of other duplicates. – Liam Commented Oct 28, 2019 at 14:08

 |  Show 1 more ment

5 Answers 5

Sorted by: Reset to default 10

You could use the algorithm of the Dutch national flag problem:

The Dutch national flag problem ¹ is a puter science programming problem proposed by Edsger Dijkstra (In a chapter of his book A Discipline of Programming Prentice-Hall, 1976). The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

var array = [3, 3, 2, 1, 3, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (array[j] < MID) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (array[j] > MID) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);

You can count the number of occurrences of 1, 2, 3 and use that info to recreate/get the sorted array:

const arr = [3, 3, 2, 1, 3, 2, 1]

const count = arr.reduce((acc, curr) => {
  acc[curr]++;
  return acc;
}, {1: 0, 2: 0, 3: 0})

arr.forEach((_, j) => {
  if (j < count[1])
    arr[j] = 1
  else if (j < count[1] + count[2])
    arr[j] = 2
  else
    arr[j] = 3
})

console.log(arr)

Because of the fact that you know that the array can contain only 3 items, you can iterate over the entire array for each one of them, (this means that the algorithm runs 3*n times = O(3n) = O(n)).

The space restriction indicates that you need to work in-place, means, work on the input array.

This is my solution :]

function swap(i, j, arr) {
  const currentVal = arr[j];
  arr[j] = arr[i];
  arr[i] = currentVal;
}

function sort(arr) {
  let globalIndex = 0;
  [1, 2, 3].forEach(item => {
    for (let i = globalIndex; i < a.length; i++) {
      if (arr[i] === item) {
        swap(i, globalIndex, arr);
        globalIndex++;
      }
    }
  });
}

const a = [1, 2, 3, 2, 1, 1];

sort(a);

console.log(a);

According to me, you can simply initialize three variables as 0 for the counts of each 1, 2 and 3. Traverse the array once and increment the corresponding counter by 1 for values at every index i.e. if the value at a particular index is 2, increment the second variable by 1.

Once, you got the counts, (Count1 - 1)th index will be the last occurrence of 1, (Count1 + Count2 - 1)th index will be the last occurrence of 2 and (Count1 + Count2 + Count3 - 1)th index will be the last occurrence of 3.

You can traverse the whole array and assign the values accordingly. This way is somewhat like Counting Sort but is of course not stable. However, you have another option as already mentioned in previous answers -Dutch National Flag Problem

I followed a simple bruteforce approach which still gives O(n) at the end. After all O(2N) + O(3) = O(N)

import sys

def sortNums(nums):
    res = {}
    mi = sys.maxsize
    ma = -1 * sys.maxsize
    mid = 0
    for i in nums: #O(n)
        if i in res:
            res[i] += 1
        else:
            res[i] = 1
        if mi > i:
            mi = i
        if ma < i:
            ma = i
    
    for ele in res.keys(): #O(3)
        if ele != mi and ele != ma:
            mid = ele

    return ([mi] * res[mi]) + ( [mid] * res[mid] ) + ([ma] * res[ma]) # O(n)

print(sortNums([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]

本文标签： javascriptsorting array of (123) numbers in O(n) timeStack Overflow