วิธีแยกค่าที่ไม่ซ้ำจากอาเรย์อย่างมีประสิทธิภาพ?

ฉันต้องการแยกค่าที่ไม่ซ้ำออกจากอาร์เรย์ (จัดสรรแบบไดนามิก) ของฉัน ฉันมีบางอย่างเช่นนี้:

    [0]     0   int
    [1]     1   int
    [2]     2   int
    [3]     2   int
    [4]     2   int
    [5]     5   int
    [6]     6   int
    [7]     6   int
    [8]     8   int
    [9]     9   int
    [10]    10  int
    [11]    8   int
    [12]    12  int
    [13]    10  int
    [14]    14  int
    [15]    6   int
    [16]    2   int
    [17]    17  int
    [18]    10  int
    [19]    5   int
    [20]    5   int

ฉันต้องการให้อาร์เรย์ขนาด 12 โดยทุกระเบียนในนั้นเป็นค่าที่ไม่ซ้ำจากอาร์เรย์อื่น

ฉันจะทำเช่นนั้นได้อย่างไร?

แก้ไข ฉันลืมบอกไปว่าฉันไม่สามารถใช้คอนเทนเนอร์ STL ได้ (เช่น std::vector หรือ std::list)


c++ arrays element unique
person Patryk    schedule 07.02.2012    source แหล่งที่มา
comment
คุณทราบค่าสูงสุดและต่ำสุดของคุณในอาร์เรย์ที่จัดสรรแบบไดนามิกหรือไม่   -  person Jayantha Lal Sirisena    schedule 07.02.2012
comment
@Jayantha ฉันสามารถรับค่านี้ได้ใช่ แต่เพื่ออะไรล่ะ?   -  person Patryk    schedule 07.02.2012
comment
@Patryk: คุณสามารถใช้อัลกอริธึม STL ได้หรือไม่?   -  person Jacob    schedule 07.02.2012
comment
@Patryk: ฉันเดาว่าคำถามของ Jayantha คือค่าคงที่และ small (ตามคำจำกัดความของ small) หรือไม่ ... อาจเป็นเจตนาคือคุณสามารถสร้างอาร์เรย์ของ N bool (หรือใช้ บิตแมป) ให้เดินผ่านอาร์เรย์ O(N) ที่ทำเครื่องหมายองค์ประกอบที่มีอยู่ จากนั้นบิตแมปจะมีชุดของค่าที่มีอยู่ในอาร์เรย์ดั้งเดิม   -  person David Rodríguez - dribeas    schedule 07.02.2012

คำตอบ (6)


arrow_upward
1
arrow_downward

ขั้นแรก คุณต้องเรียงลำดับอาร์เรย์ จากนั้นวนซ้ำอาร์เรย์ที่เรียงลำดับแล้ว และตรวจสอบว่ารายการก่อนหน้าหรือถัดไปเหมือนกับรายการปัจจุบัน ถ้าไม่เช่นนั้นค่าจะไม่ซ้ำกัน

แก้ไข: ฉันอาจเข้าใจคำถามผิด... วิธีหนึ่งที่จะได้สิ่งที่คุณต้องการคือการวนซ้ำในอาร์เรย์ สำหรับแต่ละค่า ให้ตรวจสอบค่าที่มีอยู่แล้วในอาร์เรย์อื่น หากไม่มีการคัดลอกไว้ที่นั่น ซึ่งอาจต้องทำในสองขั้นตอน ขั้นแรกเพื่อให้ได้ จำนวน ของรายการที่ไม่ซ้ำ (โดยใช้อาร์เรย์ที่มีขนาดเท่ากับที่มีอยู่) และอีกขั้นเพื่อให้ได้อาร์เรย์ที่มีขนาดถูกต้อง

person Some programmer dude    schedule 07.02.2012

arrow_upward
5
arrow_downward

ใช้ std::unique หลังจากเรียงลำดับอาร์เรย์ของคุณด้วยอัลกอริทึมการเรียงลำดับที่คุณชื่นชอบ (เช่น std::sort)

แก้ไข: หากไม่มี STL วิธีแก้ไขที่ง่ายที่สุดคือการค้นหาค่าต่ำสุด & สูงสุดในอาร์เรย์และจัดสรรอาร์เรย์ bool แบบไดนามิก สำรวจอาร์เรย์และหากคุณเห็นองค์ประกอบ ให้ตั้งค่าองค์ประกอบ bool ที่เกี่ยวข้องเป็น true จัดสรรอาร์เรย์ int ใหม่ด้วยจำนวนองค์ประกอบที่ไม่ซ้ำกันทั้งหมด และเติมข้อมูลจากอาร์เรย์ bool

แนะนำ: จัดเรียงอาร์เรย์และลบองค์ประกอบที่ต่อเนื่องกัน การใช้การเรียงลำดับอย่างรวดเร็วนั้นไม่ยากเกินไป และหากคุณกำลังจัดการกับจำนวนเต็ม การเรียงลำดับ Radix อาจจะดีกว่า

person Jacob    schedule 07.02.2012

arrow_upward
2
arrow_downward

คุณสามารถใช้ std::set ได้ เพิ่มองค์ประกอบทั้งหมดลงไป ในตอนท้ายจะมีเฉพาะค่าที่ไม่ซ้ำเท่านั้น

person Luchian Grigore    schedule 07.02.2012

arrow_upward
1
arrow_downward 

#include <iostream>
#include <stdlib.h>
using namespace std;

int cmpfun(const void * a, const void * b){
  return (*(int*)a - *(int*)b);
}
int main(){
  int n,i,j=0;
  cout<<"Enter the number of elements in the array:\n";
  cin>>n;
  int arr[n],arr_new[n];
  for(i=0;i<n;i++)
       cin>>arr[i];
  qsort(arr, n, sizeof(int), cmpfun); /*Sorting the array; if you aren't allowed to use any library sorting method,
                                   then I suggest to implement one sorting function on your own.*/

  for(i=0;i<n;i++){
       arr_new[j++]=arr[i];
        // Excluding all duplicates
       while(i<(n-1) && arr[i]==arr[i+1])
                 i++;
  }
  for(i=0;i<j;i++)
  cout<<arr_new[i]<<" ";

return 0;}

จุดมุ่งหมายหลักคือเพื่อให้แน่ใจว่าจะละเว้นข้อมูลที่ซ้ำกัน ดังนั้น คุณควรเรียงลำดับอาร์เรย์ก่อน จากนั้นในเวลา O(n) สำรวจอาร์เรย์ โดยไม่สนใจการซ้ำทั้งหมด ขณะสำรวจอาร์เรย์ ให้คัดลอกค่าที่ไม่ซ้ำกันทั้งหมด (ค่าที่คุณพบเป็นครั้งแรก) ไปยังอาร์เรย์ใหม่

สิ่งเดียวที่ฉันพบว่าทำให้คุณกังวลก็คือการเรียงลำดับองค์ประกอบในอาเรย์เก่านั้นจะไม่คงอยู่ในอาเรย์ใหม่ แต่ถ้าคุณกังวลแค่เพียงการค้นหาค่าที่ไม่ซ้ำใคร วิธีนี้ก็น่าจะใช้ได้ผลดี

person Archit Kapoor    schedule 15.05.2015

arrow_upward
0
arrow_downward

คุณสามารถใช้ชุดแฮช (unordered_set) เพื่อจัดเก็บแต่ละค่าของอาร์เรย์ต้นทาง ชุดจะจัดเก็บเฉพาะค่าที่ไม่ซ้ำโดยอัตโนมัติ จากนั้น หากคุณต้องการอาร์เรย์จริงๆ ไม่ใช่ชุด คุณสามารถสร้างอาร์เรย์ที่มีขนาดเหมาะสมและเติมองค์ประกอบต่างๆ ของชุดลงในอาร์เรย์ได้

person Baptiste Wicht    schedule 07.02.2012

arrow_upward
0
arrow_downward

หากคุณทราบค่าสูงสุดและต่ำสุด คุณสามารถสร้างอาร์เรย์ใหม่ด้วยค่าที่เป็นไปได้ทั้งหมดที่คุณจะได้รับ จากนั้นวนซ้ำผ่านอาร์เรย์ไดนามิกของคุณ สำหรับแต่ละค่า ให้ตั้งค่า 1 สำหรับอาร์เรย์ใหม่โดยใช้เป็นดัชนีของค่า เป็นตัวอย่าง:- สมมติว่าคุณมีข้อมูลเช่นนี้ 1,2,2,4,6

ถ้าช่วงเป็น 1 ถึง 7

อาร์เรย์ที่สองจะเป็นเช่นนี้

1 2 3 4 5 6 7
1 1 0 1 0 1 0

ความซับซ้อนของอัลโกจะเป็น 2n

person Jayantha Lal Sirisena    schedule 07.02.2012