Is Time Complexity is good enough? Or can be better?

[YaLeon]

the task is :
A. Write a method public boolean single (int [] values) receiving a full array values ​​with numbers, and returns true if the array is an organ that appears only once in the array, and false otherwise.
For example, for the array {3, 1, 4, 1, 4, 1} method returns true because that 3 appears only once, while for the array {3, 1, 4, 1, 4, 3} method returns false because there is no organ appears only once. (12%)

The method you write should be as efficient as possible. Answer is not effective enough, ie have greater complexity than that required to solve the problem will not get the full

my answer:

public boolean singel (int[] values)
                    {
                        for ( int i = 0 , i < values.length()-1; i ++)
                        quisort (a) ; // Time Complexity O = n(LOGn) (sorting from small to bigger)
                        if ( binarySearch (a, a[i])
                        {
                             if ( a[i] == a[values.length()-1])//chek if founded number is the last 
                             //so, in that case we need to chek if number before is not the same.
                             //need to do free chekpoint to no pass bounds array.
                                    if ( a[i] == a[values.length()-1]) 
                                         return false;
                                    else 
                                         return true;
                             if (a[i] == a[0])//if founded number first in array so need to chek only the next;
                                    if ( a[i] == a[1])
                                         return false;
                                    else 
                                        return true;
                             if (a[i]== a[i+1])||(a[i] == a[i-1])
                                         return false;
                                    else 
                                         return true;
                        }

                    }

ok, that what i do n(Logn) can i do better that that?

[YaLeon]

Will be Happy to get answers, thanks to everyone.

[Taywin]

Quick sort is one of the worst sort algorithm (O(n^2)) even though the average/best big O is nlogn. If you want to sort it, use other sort algorithms.

Anyway, what does "as efficient as possible" mean? Does it include both space and time?

One way to deal with is to create a hash, and use the number as key. Iterate through the array. If the number is duplicated, increment the counter. Once you are done, iterate through the hash key to see whether there is a value of 1. If it is, return true; otherwise, return false at the end of the method.

This will become O(n) + c. The c is a constant which comes from the time creating hash. If you want it to be more precise, this process is O(n+m) + c where n is the number of elements in the passing in array, m is the total unique numbers of the elements which m<=n, and c is still the constant of creating hash.

[YaLeon]

If you take the number you need to save it to compare. So you run complexity n ^ 2

[YaLeon]

other sorting are run complexity n^2 acept the quicsort where we take an average run complexity nlogn

[Taywin]

If you take the number you need to save it to compare. So you run complexity n ^ 2

Hmm... You need to look at how the algorithm is doing. If you are going through the incoming array (n elements), that is O(n). If you use a hash, it is always O(1) because it is not an array. The only cost, which is c, is depended on how Java create the hash in the memory. Therefore, each iteration through the existing hash after going through the array is equal to the unique element numbers (m). There is no n^2 or even near it. You need to read about how hash works.

Hash<Integer, Integer> cnt = new Hash<Integer, Integer>();

// this is O(n)
Integer k, v;
for (int i=0; i<array.length; i++) {
  k = new Integer(array[i]);
  // containsKey for hash is not an iteration check!
  if (cnt.containsKey(k)) {
    cnt.put(k, new Integer(cnt.get(k).intValue+1));  // increment count
  }
  else { cnt.put(k, new Integer(1)); }  // create a new hash which cost a constant time
}

other sorting are run complexity n^2 acept the quicsort where we take an average run complexity nlogn

Look at Merge sort, Tim sort, etc...

[YaLeon]

I wil study hash and then come back to understand your answer.
thanks.

[tux4life]

It's also possible using two HashSets, one that keeps track of the elements that occur only once, and another that keeps track of the elements that occur more than once.
At the end you check the size of the first HashSet, and if it is not empty you know that there are elements that occur only once :-)

I coded it in Java, but instead of the Java code I will post the pseudo-code for the algorithm:

SINGLE returns a boolean
    (true if there is at least one element in array that occurs only once,
     or false otherwise)

    array: an array of integers

single <- an empty set of integers
multiple <- an empty set of integers

for every integer i in array do:
    if single contains i then:
        remove i from single
        add i to multiple
    else if multiple does not contain i then:
        add i to single

return true if single is not empty, false otherwise

Have only tested it against the example in the first post.