Geek Answers Handbook

Search for a single integer in an array

I am trying to solve an issue with an algorithm. I need to find a single integer in an array

for example {1,1,5,5,5,3,2,2}

the conclusion should be 3, because the only one whole.

So far I have created an algorithm in which I first sort the array, and then check if the elements are i-1 and i + 1, and if this does not mean that I have one.

The problem is this: for short input it works fine, but for long inputs I get timeouts (it takes too much time to calculate, so my answer is not checked).

Could you give me some tips for improving the algorithm?

static int lonelyinteger(int[] a) {

    Arrays.sort(a);

    if (a.length == 1)
        return a[0];

    for (int i = 0; i < a.length; ++i) {

        if (i == 0) {
            if (a[i + 1] != a[i])
                return a[i];
        } else if (i == a.length - 1) {
            if (a[i] != a[i - 1])
                return a[i];
        } else {
            if (a[i - 1] != a[i] && a[i + 1] != a[i])
                return a[i];
        }  
    }
    return -1;
}
+4
source share
4 answers

Is O (N ^ 2) not "fast enough" for this problem?

10 000 000 . " " 5, O (N ^ 2) , . " ", .

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer

    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1)); 
    ints.set(ints.size() - 1, tempValue);

    for (int i = 0; i < ints.size(); i++) {
        boolean singleInteger = true;
        for (int j = 0; j < ints.size(); j++) {
            if (j == i) {
                continue;
            }
            if (ints.get(j) == ints.get(i)) {
                singleInteger = false;
                break;
            }
        }

        if (singleInteger) {
            System.out.println("Single instance: " + ints.get(i));
            break;
        }
    }
}

:

: 5 ( 10-20 );

Update

3 .

...

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer
    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1));
    ints.set(ints.size() - 1, tempValue);

    Map<Integer, Integer> counts = new HashMap<>();
    for (int i : ints) {
        if (counts.containsKey(i)) {
            counts.put(i, counts.get(i) + 1);
        } else {
            counts.put(i, 1);
        }
    }

    for (Integer key : counts.keySet()) {
        if (counts.get(key) == 1) {
            System.out.println("Single Instance: " + key);
        }
    }
}

:

: 5 ( 1 - 3 )

+1

, ? , , , , . , , .

, , XOR . XOR, , , , . O (n).

, , , - O (n * logn).

+1

, Arrays.sort(a);, .

,

 static int lonelyinteger(int[] a) {
    if (a[0] != a[1]) return a[0];

    int i = 1;
    while ((i < a.length - 1) && (a[i] == a[i-1] || a[i] == a[i+1])) {
        i++;
    }

    if ((i < a.length -1) || (a[i] != a[i-1]))  return a[i];
    return -1;
}
+1

. ...

while (true) {
    if (a[0] != a[1]) {
        return a[i].
  } else {
      remove all a[0]s from a.
  }
}

O (nlogn).

O (n) ( ), , , . , . , . . .

0
source

More articles:


All Articles