How to return the index array of a character in a string in Java

Question

I need to write a method to return the index array of a character in a string in Java. Is the following good (correctness, efficiency, as short code as possible) enough?

int[] charIndexArray(String s, char c) {
    int start = 0;
    List<Integer> list = new ArrayList<Integer>();
    while ((start = s.indexOf(c, start)) != -1) {
        list.add(start);
        start++;
    }
    int arr[] = new int[list.size()];
    for (int i = 0; i < ret.length; i++)
        arr[i] = list.get(i);
    return arr;
}

Not really, indexOf() return the postion and he is using it. — Damian Leszczyński - Vash
– Damian Leszczyński - Vash, Commented Apr 27, 2012 at 22:26

Eric Andres · Accepted Answer · 2012-04-27 22:25:40Z

1

You can replace the code at the end that copies it to an array with a call to the toArray() method. Other than that, looks pretty good.

answered Apr 27, 2012 at 22:25

Eric Andres

3,4172 gold badges26 silver badges41 bronze badges

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

6 Comments

Eric Andres Over a year ago

Could I get a reason for the -1?

Eric Andres Over a year ago

That's a pretty crappy reason for a -1. Down votes are for inaccurate information, not to show disagreement.

Louis Wasserman Over a year ago

Here's an objection: the toArray() method would return an Object[], and even toArray(T[]) will return an object array of some kind, which has additional overhead compared to an int[].

Eric Andres Over a year ago

@LouisWasserman - good point. I'm not a huge Java coder. I forget that you have to box and unbox so much in Java (granted, C# does it, just automatically, without the coder having to worry about it).

Qiang Li Over a year ago

if so, why you still haven't removed your answer. :)

|

Clint · Accepted Answer · 2012-04-27 23:44:23Z

1

Instead of:

while ((start = s.indexOf(c, start)) != -1) {
    list.add(start);
    start++;
}

consider:

for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == c) {
      list.add(i);
    }
 }

because the indexOf causes the creation of a whole other loop to search for the next instance of your character.

You code is quietly doing:

while (start != -1) {
    start = -1;
    for ( int i=start;i<s.length();i++){
      if ( charAt(i) == c ) {
        start = i;
        break;
      }
    }
    if ( start != -1 ) { 
    list.add(start);
    start++;
  }
}

Which does not seem more efficient. But it turns out that after spending way too much time on this:

static int[] charIndexArrayByBits(String s, char c) {
    int start = 0;
    int[] list = new int[s.length()];
    int count = -1;
    while ((start = s.indexOf(c, start)) != -1) {
      list[++count] = start;
      start++;
    }
    return Arrays.copyOf(list, count);
  }

is faster. But I would not consider it more efficient in the general case because you are allocating an int array which would be larger space wise.

edited Apr 27, 2012 at 23:44

answered Apr 27, 2012 at 22:42

Clint

9,0681 gold badge28 silver badges40 bronze badges

3 Comments

Qiang Li Over a year ago

but the overall iteration length is the same, i believe, in both cases, of course, if one can safely assume Java String is random-accessible sequence container.

Damian Leszczyński - Vash Over a year ago

Do not forget about the boxing invoved.

Qiang Li Over a year ago

right, my original solution still loop over the string once! The only place where it can be made "more" (no matter how small) efficiently is to remove the boxing/unboxing part, correct?

Damian Leszczyński - Vash · Accepted Answer · 2012-04-28 01:34:10Z

0

The code do not look good.

You use two loop instead of one.

Try to use methods.

charAt(int pos) for string and Arrays.copy

The OP shold not read more ;p

The first is the location this kind of method should be placed in some util class and be static IMHO.

public class CharSequenceUtil {

    private static int[] EMPTY_INT_ARRAY = new int[0];

    /**
    * Method search the position of given character in char sequence.
    *
    * @param CharSequence seq - Sequence of char that will be investigate 
    * @param char c - Character that is analysed.
    *
    * @return int array with positions of char c in CharSequence instanace
    * @throws NullPointerException if seq is null.
    */
    public static int[] charIndexArray(CharSequence seq, char c) {

      if(seq == null) {
        throw new NullPointerExcetion("The seq must not be null");
      }

      if(seq.length() == 0) {
        return EMPTY_INT_ARRAY;
      }

      int[] positions = new int[seq.lenth()];
      int stor = -1; 

      for(int pos = 0; pos < seq.length(); seq++) {
         if(c == seq.charAt(pos)) {
          positions[++stor] = pos;
         }
      }

      if(stor == -1) {
        return EMPTY_INT_ARRAY;
      }

      return Arrays.copyOf(positions, stor);
    }
}

edited Apr 28, 2012 at 1:34

answered Apr 27, 2012 at 22:28

Damian Leszczyński - Vash

31k9 gold badges64 silver badges95 bronze badges

4 Comments

Qiang Li Over a year ago

how so about two loops? i only see one iteration over the string.

Damian Leszczyński - Vash Over a year ago

@QiangLi, in the indexOf you have another loop and additioanl you call a method that is not really designed for this usage. It should be used when you are insterted in position and you do not want to write the whole code.

Paul Vargas Over a year ago

I think that this is the more faster way. I don't know if System.arrayCopy is more faster because is native method.

Damian Leszczyński - Vash Over a year ago

The copyOf, call System.arrayCopy, so that is the gain.

Collectives™ on Stack Overflow

How to return the index array of a character in a string in Java

3 Answers 3

6 Comments

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related