Array with loops Java

Question

I want to print put the elements in an array that only occur twice. So if, for example, number 2 occurs 3 or 4 times, it should not be printed. The code I've written so far is below. The issue in my code is with the loop. For example, for the number 2, since j=i+1 is the initialization condition, the inner loop won't read the elements before the jth location- since there is a 2 at index 6, it won't count the 2s before it, making the required condition true and displaying the 2. Is there a way to fix this?

public class Problem2 {

    public static void exactlytwice(int[] x) {
        int count, j;
        for (int i = 0; i < x.length; i++) {
            count = 0;
            for (j = i + 1; j < x.length; j++) {
                if (x[i] == x[j])
                    count++;
            }
            if (count == 1)   System.out.print(x[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] x = new int[15];
        x[0] = 2;
        x[1] = 2;
        x[2] = 2;
        x[3] = 13;
        x[4] = 44;
        x[5] = 44;
        x[6] = 2;
        x[7] = 63;
        x[8] = 63;
        x[9] = 90;
        x[10] = 1;
        x[11] = 2;
        x[12] = 150;
        x[13] = 150;
        x[14] = 180;

        exactlytwice(x);
    }
}

Answer 1

Code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class Writer {  
    private int counter; 
    private Random generator = new Random();
    private List<Integer> data = new ArrayList<Integer>();
    private Map<Integer,Integer> map = new HashMap<Integer,Integer>();

public Writer(int n){
    populate(n);
}

private final void populate(int n){
    for(int i = 0; i != n; i++){
        data.add(generator.nextInt(10));
    }
}

private final void reset(){
    this.counter = 0;
}

public final void occurence(){
    for(int dp : data){
        for(int i = 0; i < data.size(); i++){
            if(dp == data.get(i)){
                counter += 1;
            }
        }
        map.put(dp, counter);
        reset();
    }
}

public final void filter(int d){
    for(int key : map.keySet()){
        if(map.get(key) == d){
            System.out.println("Key: " + key + " Value: " + map.get(key));
        }
    }
}

public void rawData(){
    System.out.println(data.toString());
}

public void output(){
    System.out.println(map.toString());
}

Initiate:

// Create instance of Writer class and generate '100' random numbers
Writer writer = new Writer(100);

// Output raw data          
writer.rawData();

// Process data
writer.occurence();

// Filter numbers with occurence '10'
writer.filter(10);

// Output processed data
writer.output();

Output (from from calling filter(10)):

   Key: 3 Value: 10
   Key: 8 Value: 10

Answer 2

With Java 8 you can achieve this using streams like this :

public static void main(String[] args)
{
    List<Integer> list = Stream.of(12,1,3,4,2,3,7,6,7,3,1,8,4,12,33,45,78,36,8)
    .collect(Collectors.groupingBy(x->x, Collectors.summingInt(x->1)))
    .entrySet().stream().filter(x->x.getValue()==2)
    .collect(ArrayList<Integer>::new,(x,y)->x.add(y.getKey()),ArrayList<Integer>::addAll);
    System.out.println(list);
}

The result is :

[1, 4, 7, 8, 12]

Answer 3

In addition to the answers provided, there are two more ways you could go about this:

1. If array modification is permitted, change elements already encountered to a dummy value, and skip the value if encountered. This reduces the time complexity to O(n) from O(n^2), but destroys the original array. Of course, this assumes that the acceptable integers are restricted to a certain set (thanks to @Dzmitry Paulenka for reminding me that I hadn't stated this explicitly). To keep the array, you could make a copy (although then the space complexity becomes O(n) ).

2. If any integer is acceptable, then create an encountered boolean array, all intialized to false. Change the locations of elements encountered in the original array to true in the encountered boolean array, and if the value is already true, it can be skipped. Again, time complexity O(n), but O(n) space complexity, and unlike in the second method of 1., does not require the permissible range of numbers (ints) to be restricted.

3. Alternately, simply make the initialization of j as j=0, and then ensure that only those numbers which don't have that number appearing before them are printed, i.e., that the number is printed only if it occurs at j>=i (thanks to @Nir Levy for pointing the j>=i requirement out). This is (slightly) more inefficient than the code already written, but the time complexity remains the same O(n^2).

Answer 4

Just for completeness, there is a solution without extra-map. It's still O(n^2), but uses no extra memory. And It uses kind of fun idea.

First, we only need to output first occurence of a number, every other one is not relevant, because we either have more than 2 of them, or we've already output the first one.

Second, we can then indeed continue, from i+1 element, because at this point, there are no elements equal to ith, that are earlier in array.

public static void exactlytwice(int[] x) {
    int count, j;

    TOP:
    for (int i = 0; i < x.length; i++) {
        count = 0;
        for (j = 0; j < i; j++) {
            if (x[j] == x[i])
                // had this number earlier, so go to the next one.
                continue TOP;
        }
        for (j = i+1; j < x.length; j++) {
            if (i != j && x[i] == x[j])
                count++;
        }
        if (count == 1) System.out.print(x[i] + " ");
    }
}

Answer 5

aside from the issue you wrote, the bigger problem I see with your code is that its inefficient. You are doing a loop inside a loop here, which is very slow (o(n^2)).

My suggestion is to keep a map of numbers->count, and then only take the ones that appear only twice in the map:

public static void exactlytwice(int[] x) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int i = 0; i < x.length; i++) {
        if (counter.contains(i)) {
           counter.put(i,1);
        } else {
           counter.put(i,counter.get(i)+1);
        }
    }

    for (Integer i : counter.keyset()) {
        if (counter.get(i) == 2) {
          System.out.println(i);
        }
    }
}

Answer 6

1. Think about maintaining a seperate array/list which keeps track of all the elements that has been counted/printed by which you could just skip the same number that shows again down the array.

2. Or you could sort the array and then perform the whole logic to check for duplicates.