计算具有不同偶数的子集


难度级别 易得奖学金
经常问 思科 Expedia的 Myntra SAP实验室 出租车
排列 哈希 子集

在采访中的某个时候,我们都为子集问题而苦苦挣扎。 面试官也喜欢这些问题。 这些问题有助于他们检查任何学生的理解和思维过程。 因此,事不宜迟,让我们直接跳入这个问题。

第1节

问题陈述

我们已经提供了数字的组合/数组。 我们将征集具有唯一偶数的子集的数量。

让我们举一个小例子:

输入:

[1,2,5,6,3,2,1,1,8]

可能的子集:

[2,6]

[6,8]

[2,6,8]

注意:具有相同编号的子集不会被认为是不同的

让我通过突出显示可能的答案子集之一来说明这一点。

计算具有不同偶数的子集

第2节

分析

有多种方法可以找出我们想要的东西。 这 蛮力 一个是找到所有可能的子集,然后找到满足我们规则的子集。

上面的方法无非就是将头撞在墙上。 因此,为了避免听起来笨拙的尴尬,我想出了最简单的方法,可以帮助您在最佳时间获得答案。

每次遇到偶数时,我们都有两个选择

  • 它可以选择位于子集中
  • 它可以选择保留在子集中

因此,我们现在要做的唯一任务就是确定数字是否唯一。 (由于上述规则)

让我们将过程归零:

  • 首先,保持 哈希集 保留我们遇到的偶数
  • 其次,运行循环
  • 检查数字是否为偶数
  • 如果数字是偶数,我们将其添加到HashSet
  • HashSet具有自排序功能,可确保我们只有唯一的元素进入
  • 然后,我们在HashSet中找到元素的数量
  • 此计数表示我们拥有的唯一偶数的数量
  • 我们可以使用此计数来找到子集的数量
  • 子集数= 2 ^ count-1

上面的过程可以写成如下代码:

具有偶数的计数子集的Java代码

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

具有不同偶数的计数子集的C ++代码

当我们从Java切换到C ++时,我们将使用无序集而不是HashSet并浏览一些适合我们的参数。

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

具有不同偶数的计数子集的复杂度分析

时间复杂度= O(n)

空间复杂度= O(n)

时间复杂度

  • 当我们遍历数组时为O(n)
  • 在将每个元素添加到子集之前,我们会对其进行仔细研究

空间复杂度

  • 它是O(n),因为在最坏的情况下,我们可能最终会存储整个数组