ค้นหาจำนวนคู่ในอาร์เรย์เพื่อให้ XOR เป็น 0


ระดับความยาก กลาง
ถามบ่อยใน จังหวะอินเดีย คูปอง Honeywell จริง InfoEdge Moonfrog Labs Pinterest
แถว เกร็ด กัญชา ค้นหา การเรียงลำดับ

ปัญหา“ ค้นหาจำนวนคู่ในอาร์เรย์เพื่อให้ XOR เป็น 0” ซึ่งสมมติว่าเราได้ให้ไฟล์ แถว of จำนวนเต็ม. คำสั่งปัญหาขอให้ค้นหาจำนวนคู่ที่มีอยู่ในอาร์เรย์ซึ่งมีคู่ Ai แฮคเกอร์ Aj = 0

หมายเหตุ: 1 น้อยกว่าหรือเท่ากับ i, i น้อยกว่า j และ j น้อยกว่าหรือเท่ากับ n (1 <=i < j<= n)

ตัวอย่าง

ค้นหาจำนวนคู่ในอาร์เรย์เพื่อให้ XOR เป็น 0

arr[] = {2, 3, 1, 3, 2}
2

คำอธิบาย

ดัชนี (0,4) และ (1,3)

arr[] = {1, 1, 1}
3

ขั้นตอนวิธี

  1. ค้นหาองค์ประกอบสูงสุดที่มีอยู่ในอาร์เรย์
  2. สร้างอาร์เรย์ขนาด (องค์ประกอบสูงสุด)
  3. สำรวจอาร์เรย์ในขณะที่ i <n (ความยาวของอาร์เรย์)
    1. นับและจัดเก็บความถี่ของแต่ละองค์ประกอบอาร์เรย์ในอาร์เรย์ที่เราสร้างขึ้น
  4. สำรวจอาร์เรย์นับในขณะที่ i <= องค์ประกอบสูงสุด
    1. ทำ output = output + count [i] * (count [i] - 1);
  5. ส่งคืนเอาต์พุต / 2.

คำอธิบาย

เรามีอาร์เรย์ของจำนวนเต็ม คำสั่งปัญหาขอให้ค้นหาคู่ที่มีอยู่ในอาร์เรย์เช่นนั้น Ai แฮคเกอร์ Aj = 0 เราจะใช้การแมปดัชนีซึ่งหมายความว่าเราจะนับความถี่ของแต่ละองค์ประกอบอาร์เรย์เพื่อที่เราจะได้ทราบว่าพวกเขาสามารถนับ [i] * count [i-1] และผลลัพธ์เป็น เอาท์พุท ในการแก้ปัญหานี้ให้ใช้ไฟล์ แถว และในตำแหน่งขององค์ประกอบอาร์เรย์ซึ่งทำหน้าที่เป็นดัชนีของอาร์เรย์จำนวนนับที่เราจะจัดเก็บความถี่องค์ประกอบของเราดังนั้นหากพบตัวเลขในที่ใดที่หนึ่งเราจะใช้เป็นดัชนี

เราจะพบองค์ประกอบสูงสุดจากอาร์เรย์ และจากขนาดองค์ประกอบสูงสุดนั้นเราจะสร้างอาร์เรย์นี่คืออาร์เรย์นับซึ่งเราจะใช้เป็นอาร์เรย์ความถี่ เราจำเป็นต้องสำรวจอาร์เรย์และจัดเก็บจำนวนของแต่ละองค์ประกอบอาร์เรย์ จากนั้นเราจะตั้งค่าตัวแปรเอาต์พุตเป็น 0

ให้เราพิจารณาตัวอย่าง:

ตัวอย่าง

arr [] = ขนาดสูงสุดของอาร์เรย์ {2, 3, 1, 3, 2} คือ 3

i = 0, arr [i] = 2 เราจะนับ [arr [i]] + = 1 หมายความว่าดัชนีที่ 2 ขององค์ประกอบของ count จะเพิ่มขึ้น 1

i = 1, arr [i] = 3 เราจะนับ [arr [i]] + = 1 หมายความว่าดัชนีที่ 3 ขององค์ประกอบของ count จะเพิ่มขึ้น 1

i = 2, arr [i] = 1 เราจะนับ [arr [i]] + = 1 หมายความว่าดัชนีที่ 1 ขององค์ประกอบของ count จะเพิ่มขึ้น 1

i = 3, arr [i] = 3 เราจะนับ [arr [i]] + = 1 หมายความว่าดัชนีที่ 3 ขององค์ประกอบของ count จะเพิ่มขึ้น 1

i = 4, arr [i] = 2 เราจะนับ [arr [i]] + = 1 หมายความว่าดัชนีที่ 2 ขององค์ประกอบของ count จะเพิ่มขึ้น 1

เรามีอาร์เรย์ของ count เป็น count [] = {0,1,2,2}

เราจะสำรวจอาร์เรย์นี้และทุกครั้งที่เราทำ output = output + count [i] * (count [i] - 1)

และจะส่งคืนผลลัพธ์เป็นเอาต์พุต / 2

รหัส C ++ เพื่อค้นหาจำนวนคู่ในอาร์เรย์เพื่อให้ XOR เป็น 0

#include<iostream>
#include<algorithm>

using namespace std;

int calculate(int a[], int n)
{
    int *maxm = max_element(a, a + 5);
    int count[*maxm + 1] = {0};

    for(int i = 0; i < n; i++)
    {
        count[a[i]] += 1;
    }
    int output = 0;
    for(int i = 0; i < (*maxm)+1; i++)
    {
        output = output + count[i] * (count[i] - 1) ;
    }
    return output/2;
}
int main()
{
    int a[] = {2, 3, 1, 3, 2};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"XOR Pairs are : "<< (calculate(a,n));
    return 0;
}
XOR Pairs are : 2

โค้ด Java เพื่อค้นหาจำนวนคู่ในอาร์เรย์เพื่อให้ XOR เป็น 0

import java.util.Arrays;

class XORPair
{
    public static int calculate(int arr[], int n)
    {
        int max= Arrays.stream(arr).max().getAsInt();

        int count[] = new int[max+ 1];

        for (int i = 0; i < n; i++)
        {
            count[arr[i]] += 1;
        }
        int output = 0;
        for (int i = 0; i < (max) + 1; i++)
        {
            output = output + count[i] * (count[i] - 1);
        }
        return output / 2;
    }
    public static void main(String[] args)
    {
        int a[] = {2, 3, 1, 3, 2};
        int n = a.length;
        System.out.println("XOR Pairs are : "+calculate(a, n));
    }
}
XOR Pairs are : 2

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ ต้องใช้เวลา O (1) ในการเข้าถึงองค์ประกอบในอาร์เรย์ ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

ความซับซ้อนของอวกาศ

O (สูงสุด) โดยที่ Max คือองค์ประกอบสูงสุดในบรรดาองค์ประกอบทั้งหมดในอาร์เรย์