How to find the first non-repeating element?

Question

How to find the first non-repeating element in an array. Provided that you can use only 1 bit for each element of the array, and the complexity of the time should be O (n), where n is the length of the array. Please make sure that I have somehow imposed a limit on memory requirements. It is also possible that this cannot be done with just an extra bit per line item. Also, please tell me if this is possible or not?

Answer 1

I would say that there is no comparison algorithm, which can be done in O (n). Since you need to compare the first element of the array with all the others, the second with all but the first, third with all but the first = Sum i = O (n ^ 2).

(But this does not necessarily mean that the algorithm does not exist faster, see sorting. There is evidence that you cannot sort faster than O (n log n) if you use comparison - and there really is one faster: Bucket Sort, which can be done in O (n)).

EDIT . In one of the other comments, I said something about hash functions. I checked some facts about this, and here are the thoughts of the hashmap approach:

• Obvious approach (in pseudocode):

  for (i = 0; i < maxsize; i++)
      count[i] = 0;
  for (i = 0; i < maxsize; i++) {
     h = hash(A[i]);
     count[h]++;
  }
  first = -1;
  for (i = 0; i < maxsize; i++)
     if (count[i] == 0) {
        first = i;
        break;
     }
  }
  for (i = 0; hash(A[i]) != first; i++) ;
  printf("first unique: " + A[i]); 
  

• There are some caveats:

  • hash. -. , O (n). ( . - , , , O (n), ( , , , , , , , - ( )). , , O (n).

  • - . , , - 2,7 . count ( : Empty + 1 Element + 1 Element) 2 (1.58, , - 2.7), 5 .

Answer 2

, - , , Integer (32 ), 26 . 256 , 256 * 32 . 32 . , , , . , (32 ) 26 :

 int print_non_repeating(char* str)
 {
  int bitmap = 0, bitmap_check = 0;
  int length = strlen(str);
  for(int i=0;i<len;i++)
  {
   if(bitmap & 1<<(str[i] - 'a'))
     {
        bitmap_check = bitmap_check | ( 1 << (str[i] - 'a');
      }
   else 
      bitmap = bitmap | (1 << str[i] - 'a');
  }
  bitmap = bitmap ^ bitmap_check;
  i = 0;
  if(bitmap != 0)
  {
  while(!bitmap & (1<< (str[i])))
   i++;
  cout<<*(str+i);
   return 1;
  }
  else 
  return 0;
  }

Answer 3

. havent , for, ( O (n)). , O (n ^ 2)

#include <iostream>
using namespace std;
#define max_size 10

int main()
{
    int numbers[max_size] = { 1, 2, 3, 4, 5, 1, 3, 4 ,2, 7};
    int table[max_size] = {0,0,0,0,0,0,0,0,0,0};
    int answer = 0, j=0;

  for (int i = 0; i < max_size; i++)
  {
    j = numbers[i] %max_size;
    table[j]++;
    if(table[j] >1)
    {
          answer = 1;
          break;
    }
 }
   std::cout << "answer = " << answer ;
}

Answer 4

You can try to make a modified bucketsort as shown below. However, you need to know the maximum value in the array passed to the firstNonRepeat method. Thus, this is true for O (n). For methods based on comparison, theoretically fast (at least in terms of sorting) is O (n log n). In addition, you can even use modified versions of radix collation to accomplish this.

public class BucketSort{
    //maxVal is the max value in the array
    public int firstNonRepeat(int[] a, int maxVal){
        int [] bucket=new int[maxVal+1];

        for (int i=0; i<bucket.length; i++){
            bucket[i]=0;
        }

        for (int i=0; i<a.length; i++){
            if(bucket[a[i]] == 0) {
                bucket[a[i]]++;             
            } else {
                return bucket[a[i]];
            }
        }
    }
}