Remove zero values from array

Question

I have an array with zero values, and I wish to copy this array to other array but without the zero values. How can I do this if determining the array size is not possible because I do not know how many zeros are there. Please note that I can not use List or ArrayList because of reasons.

// frame is the original array

final int[] sorted = new int[??];

for (int i = 0; i < frame.length; i++) {
    if (frame[i] != 0) {
        sorted[i] = frame[i];
    }
}

Most likely this is homework, and the professor is looking for the OP to learn algorithmically what is necessary which is why List and ArrayList cannot be used. Are there any other constraints to this problem??? — trumpetlicks
– trumpetlicks, Commented Feb 26, 2014 at 13:53
Nice one... Actually no. I get this array from external device that connected to the phone. I get this array 9 time per second and I need to sort it without zeros. The reason I cannot use ArrayList because it to slow to cast Array to ArrayList and it causes lag to the app. If I had faster processor (Testing on S2) maybe I could use ArrayList. — Dim
– Dim, Commented Feb 26, 2014 at 15:47
And thanks for the answer. Actually I hoped It can be done in O(n), but O(2n) it fine also. — Dim
– Dim, Commented Feb 26, 2014 at 15:49
In complexity theory there really is no O(2n). O(2n) actually IS O(n). Both 2n and n are considered LINEAR time, hope this is also helpful :-) — trumpetlicks
– trumpetlicks, Commented Feb 26, 2014 at 15:55
You right, but the array in size is about 120,000. Each second instead of 9 iteration I make 18, twice on same array, try to tell my android processor that O(n)=O(2n). This little difference make it hard on it. Thanks Again! — Dim
– Dim, Commented Feb 26, 2014 at 16:06

trumpetlicks · Accepted Answer · 2014-02-26 13:21:15Z

1

The only way I know how to do this with your given constraints would be to COUNT FIRST, Process NEXT:

unsigned int nonZeroCount = 0;

// Count the amount of non-zero values
for (int i = 0; i < frame.length; i++){
    if (frame[i]!=0)
        nonZeroCount++;
}

// Create the NEW Array
final int[] sorted = new int[nonZeroCount];

// NEXT add them to your new array, Need to have 2 separate counters, 1 for your initial array,
// Another for where you are placing it within your new array
unsigned int anotherCount = 0;
for (int i = 0; i < frame.length; i++){
    if (frame[i]!=0){
        sorted[anotherCount ] = frame[i];
        anotherCount++;
    }
}

answered Feb 26, 2014 at 13:21

trumpetlicks

7,0552 gold badges21 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Gabriel Câmara · Accepted Answer · 2014-02-26 13:30:13Z

1

Try the following:

String validNumbers = "";

for (int i = 0; i < frames.length; i++) {
 if (frames[i] != 0)
   validNumbers += (i > 0 ? ";": "")+frames[i];
}

String sorted[] = validNumbers.split(";");

This way, You'll have an array of String with the numbers that are different of 0;

answered Feb 26, 2014 at 13:30

Gabriel Câmara

1,24915 silver badges22 bronze badges

4 Comments

trumpetlicks Over a year ago

This might actually be the slowest of all of the answers. Inside of a string, Im not completely sure how it does it's memory allocations, but at worst it will do a memory allocation (often considered one of the heaviest taxing burdens in a program) for each non-zero element you add!!! I wont down-vote, because it is technically correct, but it also uses more memory (n-1) semicolons.

trumpetlicks Over a year ago

Also, this does not actually answer the OPs question, as it is specific to arrays, and most likely for a class, that he has no ability to change the use model.

Gabriel Câmara Over a year ago

You're right about the memory allocation, but not about being the slowest way. A simple JUnit test showed that the time to execute your algorithm was the same to execute mine. But yours gain in memory usage, mine was 7x more memory usage in comparison with yours =)

trumpetlicks Over a year ago

Glad you ran the JUnit tests :-) Again since java's String implementation is essentially hidden from us, the only way to KNOW is to test timing. I knew that it would use more memory. I think that Java's String implementation does a form or pre-allocation, and so long as your continual concatenation doesn't go past it, than time wise it will be the same as my version's single allocation. Always heavily depends on implementation :-) Good work!

MysticMagicϡ · Accepted Answer · 2014-02-26 13:34:31Z

1

Yo can do this if it must use array:

int j = 0;

for (int i = 0; i < frame.length; i++) {
    if (frame[i]!=0) {
        j++
    }
}

final int[] sorted = new int[j];
j = 0;
for (int i = 0; i < frame.length; i++) {
    if (frame[i]!=0) {
        sorted[j] = frame[i];
        j++;
    }
}

edited Feb 26, 2014 at 13:34

answered Feb 26, 2014 at 13:18

MysticMagicϡ

28.8k16 gold badges77 silver badges126 bronze badges

2 Comments

Dmitrii Bychenko Over a year ago

Sorry, but if frame has zero(s) the code will end with out of range error: "sorted[i] = frame[i]" will fail when i is big enough.

MysticMagicϡ Over a year ago

@DmitryBychenko right. missed completely.. edited :) thanks for pointing out

exception1 · Accepted Answer · 2014-02-26 13:18:03Z

0

I do not know much zeros there is.

So why don't you fond out?

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

answered Feb 26, 2014 at 13:18

exception1

1,2498 silver badges17 bronze badges

Comments

Slimu · Accepted Answer · 2014-02-26 13:18:38Z

0

You could make a new array with the same size like the one you test. After that you iterate over the array and for each non zero value you found, you add it, while increasing a counter that will represent the number of non zero elements found. After this you can use it to create a new array where to copy your values or simple use the counter as a upper bound when iterating the new array.

answered Feb 26, 2014 at 13:18

Slimu

2,3811 gold badge24 silver badges29 bronze badges

Comments

Melquiades · Accepted Answer · 2014-02-26 13:29:48Z

0

int noneZeroCount= 0;

for (int i = 0; i < frame.length; i++) {
    if (frame[i]!=0) {
        noneZeroCount++;
    }
}

final int[] sorted = new int[noneZeroCount]; 

// You got size of non zero elements in array now run copy loop

edited Feb 26, 2014 at 13:29

Melquiades

8,5981 gold badge36 silver badges48 bronze badges

answered Feb 26, 2014 at 13:21

Yahya Arshad

1,6282 gold badges19 silver badges34 bronze badges

Collectives™ on Stack Overflow

Remove zero values from array

6 Answers 6

Comments

4 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

4 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related