數組的兩個子集的最大可能差


難度級別
經常問 Atlassian的 Cadence印度 指令 免費收費 Opera 瀏灠器 PayU Snapchat 時代互聯網 Xome
排列 哈希 排序

假設我們有一個 整數 排列。 問題陳述“陣列的兩個子集的最大可能差”要求找出陣列的兩個子集之間的最大可能差。

要遵循的條件:

  • 數組可以包含重複元素,但是元素的最高頻率不應大於2。
  • 您應該製作兩個子集,以使它們各自元素之和之間的差異最大。
  • 數組的所有元素都應在兩個子集之間劃分,而不會留下任何元素。
  • 子集中的兩個元素不應相同。

數組的兩個子集的最大可能差

arr[] = {2, 5, -3, -1, 5, 7}
13

解釋

子集→(2,7,5)-(-3,-1,5)= 13

{1, 5, 3, -1, -5, 6}
21

解釋

子集→(1、3、5、6)–(-5,-1)= 21

算法

  1. 聲明兩個 地圖,一個代表正數,另一個代表負數。
  2. 將陽性元素及其數量存儲在一張地圖中。
  3. 繼續將所有具有頻率1的正元素相加並將其存儲在 子集1.
  4. 將否定元素及其計數存儲在另一張地圖中。
  5. 繼續將所有具有頻率1的負元素相加並將其存儲在 子集2.
  6. 返回subset1-subset2。

解釋

我們給了 排列,我們需要找出兩個子集的元素之和之間的差,且該差應為最大。 我們將使用 地圖. 哈希 提供了解決此問題的有效方法。 我們將使用兩個地圖。 一種是對正面要素進行已完成的操作,另一種是針對負面要素進行的。 數組可以同時包含正負元素,因此我們也必須處理該問題。

我們將獲取一個數組並映射。 我們將選擇數組的每個元素,並檢查其是否大於0。然後,將其與出現次數一起存儲在映射中。 存儲正數元素的頻率後,我們將對一個大於0並且頻率僅為1的數組的所有值求和,這意味著我們需要忽略那些出現多次或多次的元素。

對於負數元素,將執行相同的操作,我們將選擇數組中的每個元素,這一次,我們將檢查它是否小於0。我們將把它的數目存儲在映射中(使其為正數)。發生。 存儲負數元素的頻率之後,我們將對所有小於0且頻率僅為1的數組的值求和。在這裡,我們還需要忽略出現數次或更多的元素不止一次。

在獲得所有正負元素的和後,條件僅是那些元素的頻率為1,我們需要返回兩個和之差,這就是我們的答案。

推薦碼

C ++代碼查找數組兩個子集的最大可能差

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

Java代碼查找數組的兩個子集的最大可能差

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

複雜度分析

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 因為我們使用了HashMap,所以我們能夠在O(1)中執行插入/刪除/搜索。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。