Tìm phần tử xuất hiện sau khi

Question

Tìm phần tử xuất hiện sau khi

Cho một mảng nơi mọi phần tử xuất hiện ba lần, ngoại trừ một phần tử chỉ xuất hiện một lần. Tìm phần tử xảy ra một lần.

Độ phức tạp về thời gian dự kiến ​​là không gian thêm O (n) và O (1).

Ví dụ:

Input: arr [] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

Output: 2

Answer 1

Nếu O (1) không gian hạn chế đã không có, bạn có thể đã đi cho một hashmap với các giá trị là số lần xuất hiện.

int getUniqueElement(int[] arr) 
{ 
    int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once. 
    int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice. 
    int not_threes ; 

    for(int x : arr) 
    { 
     twos |= ones & x ; //add it to twos if it exists in ones 
     ones ^= x ; //if it exists in ones, remove it, otherwise, add it 

     // Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero. 

     not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes. 
     ones &= not_threes ;//remove x from ones 
     twos &= not_threes ;//remove x from twos 
    } 
    return ones; 
} 

Về cơ bản, nó sử dụng thực tế là x^x = 0 và 0^x=x. Vì vậy, tất cả các yếu tố kết hợp có được XOR'd và biến mất rời khỏi yếu tố cô đơn.

Tóm tắt:

Nếu một chút đã có sẵn, hãy thêm nó vào cặp đôi.

XOR sẽ thêm bit này vào bit nếu không có hoặc xóa bit này khỏi bit nếu nó đã ở đó.

Nếu một bit nằm trong cả hai cái và cặp đôi, hãy xóa nó ra khỏi những cái và cặp đôi.

Khi hoàn tất, các thẻ đó chứa các bit chỉ xuất hiện 3 * n + 1 lần, là các bit cho phần tử chỉ xuất hiện một lần.

Answer 2

Như được mô tả here, Có thể tìm thấy trung bình các phần tử của mảng trong trường hợp xấu nhất O (n) và O (1). Vì vậy, chúng tôi có thể giải quyết vấn đề bằng phương pháp phân chia và chinh phục:

Tìm thời gian trung bình trong O (n) và đếm số phần tử nhỏ hơn hoặc bằng trung vị trong O (n). Nếu con số này là 3k + 1, điều đó có nghĩa là câu trả lời nhỏ hơn hoặc bằng trung bình, vì vậy hãy bỏ qua các phần tử lớn hơn trung bình trong O (n). Khác, bỏ qua những cái nhỏ hơn hoặc bằng trung vị. Sau đó đệ quy tìm câu trả lời trong các phần tử còn lại trong T (n/2). Lưu ý: số phần tử còn lại là n/2 vì chúng tôi đã bỏ qua một nửa phần tử.

Vì vậy, T (n) = T (n/2) + O (n) = O (n) và chúng ta cần O (1) khoảng trống thừa.

Answer 3

Tôi đề xuất một giải pháp tương tự như giải pháp được đề xuất bởi mhsekhavat. Thay vì xác định trung bình, tôi đề xuất sử dụng thuật toán phân vùng của bài toán quốc gia Hà Lan http://en.wikipedia.org/wiki/Dutch_national_flag_problem (vâng, tôi là người Hà Lan và được đào tạo theo phong cách Dijkstra).

Kết quả của việc áp dụng thuật toán là mảng được phân đoạn trong phần màu đỏ, trắng và xanh dương. Phần màu trắng có thể được coi là trục. Lưu ý rằng phần màu trắng bao gồm tất cả các phần tử bằng trục, do đó phần màu trắng sẽ tồn tại 1 hoặc 3 phần tử. Phần màu đỏ bao gồm các phần tử nhỏ hơn trục và phần màu xanh bao gồm các phần tử lớn hơn trục xoay. (Lưu ý rằng các phần màu đỏ và xanh dương không được sắp xếp!)

Tiếp theo, đếm số phần tử của các phần màu đỏ, trắng và xanh dương. Nếu bất kỳ phần nào bao gồm 1 phần tử, thì đó là số bạn đang tìm kiếm.Nếu không, phần màu đỏ hoặc xanh bao gồm 3k + 1 phần tử, với một số k nhất định. Lặp lại thuật toán trên phần bao gồm 3k + 1 phần tử. Cuối cùng, một trong các phần sẽ có kích thước 1.

Thuật toán chạy trong O (n) và cần O (1) biến.

Answer 4

giải pháp JavaScript:

function findElement(arr) { 
    var ones = 0; 
    var twos = 0; 
    for (var i = 0; i < arr.length; i++) { 
    ones = (ones^arr[i]) & ~twos; 
    twos = (twos^arr[i]) & ~ones; 
    } 
    return ones; 
} 

Answer 5

Mặc dù câu hỏi đã được trả lời, tôi thấy như sau trực quan hơn và do đó thêm nó như là một câu trả lời. Nguyên từ here

int singleNumber(vector<int>& nums) { 
    /*Bits in 'ones' are set to 1, when that particular bit 
     occurs for the first time. Bits in 'twos' are set to 1, 
     when that particular bit occurs for the second time. If a 
     bit is occurring for more than 2 times, we throw it away 
     and start counting again.*/ 
    int ones = 0; 
    int twos = 0; 
    for (auto elem : nums) { 
     int onesOld = ones; 
     /* (ones^elem): consider the ith bit in 'ones' be 0 (i.e. ith 
      bit has not occurred till now or has occurred 2 times) and in 
      'elem' be 1. So, for the ith bit (ones^elem) gives 1. Now, 
      ith bit could have occurred even number of times as well (i.e. 
      ith bit in twos is set to 1). If that was the case, we 
      would like to ignore such bit. This last part is taken care 
      of by '&' with '~twos' 
      */ 
     ones = (ones^elem) & ~twos; 
     /* (onesOld & elem) gives the bits which have occurred ones 
      and also occur in this particular element. (twos & ~elem) 
      gives the bits that have occurred twice and do not occur 
      in this element. Both these cases take care of the bits 
      that have occurred 2 times (although a bit might be set 
      more than 2 times, like 5,7... but we take only modulo 3 
      count). 
     */ 
     twos = (onesOld & elem) | (twos & ~elem); 
    } 
    return ones; 
}