C++程序寻找数组中最少出现的元素

给定一个数组，找出其中出现次数最少的元素。如果有多个元素出现次数相同，则任选一个打印即可。

示例：

输入：arr[] = {1, 3, 2, 1, 2, 2, 3, 1}
输出：3
3在给定的数组中出现的最少次数。

输入：arr[] = {10, 20, 30}
输出：10或20或30

一个 简单的解决方案 是运行两个循环。外部循环一个一个地挑选所有元素。内部循环找出挑选的元素的频率并与迄今为止的最小值进行比较。这个解决方案的时间复杂度是O(n 2)。

更好的解决方案是排序。我们首先对数组进行排序，然后线性遍历数组。

// CPP program to find the least frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;

int leastFrequent(int arr[], int n)
{
    // Sort the array
    sort(arr, arr + n);

    // find the min frequency using linear traversal
    int min_count = n+1, res = -1, curr_count = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1])
            curr_count++;
        else {
            if (curr_count < min_count) {
                min_count = curr_count;
                res = arr[i - 1];
            }
            curr_count = 1;
        }
    }

    // If last element is least frequent
    if (curr_count < min_count)
    {
        min_count = curr_count;
        res = arr[n - 1];
    }

    return res;
}

// driver program
int main()
{
    int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << leastFrequent(arr, n);
    return 0;
}

输出：

时间复杂度： O(n Log n)

辅助空间： O(1)

一个 高效的解决方案 是使用哈希。我们创建一个哈希表，将元素和它们的频率计数作为键值对进行存储。最后，我们遍历哈希表并打印具有最小值的键。

// CPP program to find the least frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;

int leastFrequent(int arr[], int n)
{
    // Insert all elements in hash.
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++)
        hash[arr[i]]++;

    // find the min frequency
    int min_count = n+1, res = -1;
    for (auto i : hash) {
        if (min_count >= i.second) {
            res = i.first;
            min_count = i.second;
        }
    }

    return res;
}

// driver program
int main()
{
    int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << leastFrequent(arr, n);
    return 0;
}

输出：

时间复杂度： O(n)

辅助空间： O(n)