第一个非重复元素  


难度级别 易得奖学金
经常问 贝尔扎巴尔 科姆利媒体 大都会人寿 Snapdeal Sprinklr 胡克
排列 哈希 搜索

给我们一个数组A。我们必须找到数组中的第一个非重复元素。

使用案列  

输入:

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

输出:

第一个非重复元素是:3

因为1、2不是答案,因为它们在重复,而4不是答案,因为我们必须找到第一个non_repeating元素,即3,而不是4。

方法1:蛮力  

大意

对于中的每个元素 排列,我们将遍历整个数组,如果该元素是非重复的,那么我们将只打印该元素。

算法

  1. 对0到n-1的I进行循环
    1. 对0到n范围内的j运行循环
      1. 如果j等于n,则打印A [i]并返回。
      2. 如果I不等于j并且A [i]等于A [j],则从此循环中断。
    2. 打印所有元素在数组中重复的信息。

第一个非重复元素的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA程序

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

第一个非重复元素的复杂度分析

时间复杂度

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

参见
字符串Leetcode解决方案的反向元音

空间复杂度

我们没有使用任何多余的空间,因此空间复杂度为 O(1).

方法2:使用哈希  

大意

我们可以将每个元素的频率存储在哈希表中,然后遍历数组并找到频率为1的第一个元素。

算法

  1. 将每个元素的频率存储在哈希表中。
  2. 对0到n-1的I进行循环
    1. 如果哈希表中A [i]的频率为1,则打印A [i]并返回。
  3. 打印数组中所有重复的元素。

举例说明

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

然后,哈希表将如下所示:

第一个非重复元素Pin

第一个非重复元素的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    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)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA程序

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

第一个非重复元素的复杂度分析

时间复杂度

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

参见
大小为k的所有子数组的最小和最大元素的总和

空间复杂度

我们正在维护一个哈希表,因此空间复杂度为 上).

參考資料