数组中的第K个不同元素


难度级别 中等
经常问 土砖 亚马逊 Apple ByteDance 易趣 Expedia的 Facebook 谷歌 LinkedIn 微软 神谕 Salesforce的 Spotify 沃尔玛实验室
分而治之

给你一个整数 排列 A,在数组中打印第k个不同的元素。 给定的数组可能包含重复项,并且输出应在数组的所有唯一元素中打印第k个不同的元素。 如果k大于多个不同的元素,则报告它。

使用案列

输入:

A [] = {3,4,4,1,2,3}

K = 2

输出:

第K个非重复元素为2。

说明:

第一个非重复元素为1

第二个非重复元素是2。

方法1:蛮力

大意

我们将维护一个count变量,该变量将存储我们发现的非重复元素的数量。 现在我们将遍历所有元素,对于每个元素,我们将遍历数组以检查这是否是一个非重复元素,如果是,则将计数加1。等于K,我们将打印该元素。

阵列中第K个不同元素的算法

  1. 用零初始化变量计数,该变量计数将计算数组中不同元素的数量。
  2. 对0到n-1的I进行循环
    1. 声明一个带有false的标志,如果A [i]是一个重复元素,则为true,反之亦然
    2. 对j进行循环,范围为0到n-1
      1. 如果I不等于j并且A [i]等于A [j],则分配flag = true并中断
    3. 如果该标志为假,则将计数递增1
    4. 检查计数是否等于K,则打印A [i]。
  3. 返回

实施

C ++程序

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = 0; j < n; j++)
        {
            if (i != j and A[i] == A[j])
            {
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA程序

public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            for (int j = 0; j < n; j++)
            {
                if (i != j && A[i] == A[j])
                {
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

数组中第K个不同元素的复杂度分析

时间复杂度

我们使用两个大小均为N的嵌套循环。因此,总时间复杂度为 O(N ^ 2).

空间复杂度

我们没有使用任何多余的空间,所以空间复杂度是 O(1).

方法2:使用哈希

大意

我们将数组每个元素的频率存储在哈希表中。 现在,我们将维护一个count变量,该变量将存储我们发现的非重复元素的数量。 接下来,我们将遍历所有元素,对于每个元素,我们将检查其频率是否大于1,如果它等于1,则将计数增加1。等于K,我们将打印该元素。

阵列中第K个不同元素的算法

  1. 声明一个哈希表,该表将存储数组中每个元素的频率。
  2. 用零初始化变量计数,该变量计数将计算数组中不同元素的数量。
  3. 对0到n-1的I进行循环
    1. 如果A [i]的频率为1,则将计数加1。
    2. 如果计数等于K,则打印A [i]。
  4. 返回

例如:

A [] = {3,4,4,1,2,3}

K = 2

哈希表看起来像这样,

数组中的第K个不同元素

实施

C ++程序

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA程序

import java.util.*; 
public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        HashMap <Integer, Integer> hash_table = new HashMap<Integer, Integer> ();  
        for (int i = 0; i < n; i++)  
        { 
            if(hash_table.containsKey(A[i])) 
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            else
                hash_table.put(A[i], 1); 
        } 
        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

数组中第K个不同元素的复杂度分析

时间复杂度

我们仅对数组进行两次迭代。 因此,总时间复杂度为 上).

空间复杂度

我们正在维护一个哈希表,以存储数组中元素的频率。 因此,空间复杂度为 上).

參考資料