排序数组并将所有重复的元素移到末尾

Question

我在最近的面试中遇到过这个问题。

给出一个数组，我需要对数组进行排序，所有重复的元素都应该在末尾。

输入：{7,4,2,3,3,5,3,11,9,2}

因为2和3是重复的元素，所以它们应该发生在Array的末尾。

产出：{4,5,7,9,11,2,2,3,3,3}

我可以自由使用任何其他数据结构。没有约束。

Answer 1

CREATE_ARRAY repeated, unique
SORT inputArray
ADD MINIMAL_POSSIBLE_VALUE TO inputArray
TRAVERSE inputArray i=index (from 2nd element to last):
   IF inputArray[i-1] == inputArray[i]:
      2X: ADD inputArray[i] TO repeated
      i++
      WHILE i < LENGTH(inputArray) - 1 and inputArray[i-1] == inputArray[i]:
         ADD inputArray[i] TO repeated
         i++
   ELSE:   
      ADD inputArray[i-1] TO unique
PRINT MERGED(unique, repeated)

您将对数组进行排序，以便复制值形成修补程序。然后将数组分发到唯一值数组和重复值数组，并将两者打印出来。

第三行ADD MINIMAL_POSSIBLE_VALUE TO inputArray只是向数组中添加了一个虚拟元素，这个元素永远不会被打印出来，但是会为您保存一些IF语句。

​

// algorithm
function algorithm(input) {
  input.sort(function(a, b) { return a - b });
  input.push(Number.MIN_VAL);
  var repeated = [], unique = [];
  for (var i = 1; i < input.length; i++) {
    if (input[i - 1] == input[i]) {
      repeated.push(input[i], input[i]);
      i++;
      while (i < input.length - 1 && input[i - 1] == input[i]) {
        repeated.push(input[i]);
        i++;
      }
    } else {
      unique.push(input[i - 1]);
    }
  }
  return unique.concat(repeated);
}

// driver
inputBox = document.getElementById('input-box');
outputBox = document.getElementById("output-box");
inputBox.addEventListener("keyup", function() {
  outputBox.innerHTML = algorithm(inputBox.value.split(/[\s,]+/).map(Number));
});

<input id="input-box">
<div id="output-box"></div>

​

Answer 2

使用列表排序方法的C#解决方案

        static void Main(string[] args)
    {
        List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2, 5 };

        List<int> tmp = new List<int> { };
        List<int> rep = new List<int> {};

        //sorting the list
        list.Sort();

        for (var i = 0; i < list.Count(); i++) 
        {
            int cantidad = list.LastIndexOf(list[i]) - list.IndexOf(list[i]);
            if ( cantidad != 0)
            {
                //found repetitions
                rep.AddRange(list.GetRange(list.IndexOf(list[i]), cantidad + 1));
                i += cantidad;
            }
            else tmp.Add(list[i]);
        }
        tmp.AddRange(rep);

        foreach (int data in tmp)
            Console.WriteLine(data);

        Console.ReadLine();
    }

用C#手工排序的解决方案

        static void Main(string[] args)
    {
        List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2 };

        List<int> tmp = new List<int> {};
        List<int> rep = new List<int> {};

        foreach (int data in list)
        {
            if (tmp.Count() > 0)
            {
                int posicion = -1;
                bool bandera = false;
                for (var i=0; i < tmp.Count(); i++)
                {
                    //searching a repetition
                    if (tmp[i] == data)
                    {
                        tmp.RemoveAt(i);
                        //adding to the repeated list at the end or in a determined position
                        for (var j = 0; j < rep.Count(); i++)
                        {
                            if (rep[j] > data)
                            {
                                bandera = true;
                                rep.Insert(j, data); //the one that was deleted
                                rep.Insert(j, data); //the one at the original list
                                break;
                            }
                        }
                        if (!bandera)
                        {
                            bandera = true;
                            rep.Add(data); //the one that was deleted
                            rep.Add(data); //the one at the original list
                        }
                        break;
                    }
                    //saving the position to be inserted
                    if (tmp[i] > data)
                    {
                        posicion = i;
                        break;
                    }
                }
                //was not a repetition
                if (!bandera)
                {
                    bool banderaRep = false;
                    //searching in the repeated list
                    for (var i = 0; i < rep.Count(); i++)
                    {
                        if (rep[i] == data)
                        {
                            banderaRep = true;
                            rep.Insert(i, data);
                            break;
                        }
                    }
                    //was not in the repeated list
                    if (!banderaRep)
                    {
                        if (posicion == -1)
                            tmp.Add(data);
                        else
                            tmp.Insert(posicion, data);
                    }
                }
            }
            else
                tmp.Add(data);
        }
        //join
        tmp.AddRange(rep);

        foreach (int data in tmp)
            Console.WriteLine(data);

        Console.ReadLine();
    }

Answer 3

使用地图数据结构的解决方案，虽然不是一个非常有效的解决方案，但仍然有效：

1>遍历地图中数的向量计数频率

2>迭代映射(元素按排序顺序)，在向量中推送唯一的元素，在另一个向量中推送重复的元素

3>推送排序数组中的重复元素

C++中的代码

vector<int> sortUnique(const vector<int> & nums) {

// Step 1
map<int, int> numFreq;
for (auto it : nums) {
    if (numFreq.count(it) == 0) {
        numFreq[it] = 1;
    }
    else {
        numFreq[it]++;
    }
}

// Step 2
vector<int> sorted;
sorted.reserve(nums.size());
vector<int> repeated;
repeated.reserve(nums.size());
for (auto it : numFreq) {
    if (it.second == 1) {
        sorted.push_back(it.first);
    }
    else {
        for (int i = 0; i < it.second; i++) {
            repeated.push_back(it.first);
        }
    }
}
// Push repeated elements at the end
for (auto it : repeated) {
    sorted.push_back(it);
}
return sorted;
}