2

For this Algorithm assignment in class I have to find all the unique values in a 1000x250 2D array.

The data is between 2000000 to 2200000. All the data is stored in a 2D int array called data.

The problem I am having is that it takes a bit of time to run this and my prof said we can't use other data sets and also we need to optimize our code so it runs at a good speed.

    int[] uniqueValues = new int[200000];
    boolean isUnique = true;
    int uniqueCounter = 0;

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

         for (int j = 0; j < data[i].length; j++) {

            for (int x = 0; x < uniqueCounter; x++) {

                if (data[i][j] != uniqueValues[x]) {
                    isUnique = true;
                } else {
                    isUnique = false;
                    break;
                }

            }

            if (isUnique) {
                uniqueValues[uniqueCounter] = data[i][j];
                uniqueCounter++;
            }

        }
}
Cœur
  • 37,241
  • 25
  • 195
  • 267
Manny Sran
  • 173
  • 4
  • 18
  • 1
    This question should go to code review: http://codereview.stackexchange.com/ – Sweeper Sep 20 '15 at 00:28
  • 3
    *"my prof said we can't use other data sets"* - That doesn't make sense. Probably you have mistranslated it. What did he *actually* say? – Stephen C Sep 20 '15 at 00:37
  • You should use a Set. If you are not allowed to use the pre-defined Set implementation, then you should create your own Set data structure. – Michael Aaron Safyan Sep 20 '15 at 00:40
  • Also, did your "prof" say that you have to optimize it? 'Cos his (apparent) instructions to not create a separate data structure makes the obvious efficient solutions impossible. I suspect that he wants you to learn about arrays and loops in this exercise ... and this "make it go fast" is a non-requirement that you shouldn't be wasting your time one. – Stephen C Sep 20 '15 at 00:41

1 Answers1

1

Well if you allocate 200000 ints for the result anyway, you can use them as counters for each value, then collect the ones that only occur once:

for (int i = 0; i < data.length; i++) {
  for (int j = 0; j < data[i].length; j++) {
    uniqueValues[data[i][j] - 2000000]++;
  }
}        

int uniqueCounter = 0; 
for (int i = 0; i < uniqueValue.length; i++) {
  if (uniqueValues[i] == 1) {
    uniqueValues[uniqueCounter++] = i + 2000000;
  }
}
Stefan Haustein
  • 18,427
  • 3
  • 36
  • 51