questions with a while loop that has two pointers

Question

I am trying to find duplicate segments in a Java array that was sorted by Arrays.sort(). I am expecting the same ints to form a duplicate segment in the array. For example, after sorting, the array is: {1, 2, 3, 3, 3, 3, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9, 9}

I want to implement my following idea to find the duplicate segments: I want to use a while-loop with two pointers (i, and j).

1.) Let i start from the index 0, and let j start the last index (N-1). 2.) Keep i at the index 0 while doing j--. When j reaches the next index of i and no segments found, increment i by 1, and reinitialize j to index N-1 3. ) repeat steps 1 and 2. If a segment is found, increment i to j's current index, and reinitialize j to the index N-1. 4.) exit the while loop when i==j.

Below is my attempt, but it does not from my execution.

int[] test = new int[] {1, 2, 3, 3, 3, 3, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9, 9};
        int i = 0;
        int j = test.length - 1;
        int[] copySegment;

        while (j > i)
        {
            if (test[j] == test[i])
            {
                int segmentLength = j - i + 1;
                copySegment = new int[segmentLength];
                for (int k = j; k >= i; k--)
                {
                    copySegment[segmentLength--] = test[k];
                }
                for (int e : copySegment)
                {
                    System.out.print(e + " ");
                }
            }
            j--;
            i++;
        }

Answer 1

if you are trying to find the duplicate variables in your array and print the duplicates, may be you should start both the indexes from the beginning that is i=0, j=i+1

Arrays.sort(array); //sorts the array elements in ascending order
int i,j,lastNum;
ArrayList<Integer> list = new ArrayList<Integer>();

for(i=0,j=i+1;i<array.length-1;i++,j++) {
  if(!list.isEmpty()) {
    lastNum = list.get(list.size()-1);
  } else {
    lastNum = array[i]-1; // so that compiler doesn't warn you about lastNum not being initialized
  }
  if(array[i]!=lastNum) {
      if(array[i]==array[j]) {
        list.add(array[i]);
      }
  } else {
    continue;
  }
}

Iterator<Integer> it = list.iterator();

while(it.hasNext()) {
    System.out.println(it.next().intValue());
}

EDIT: I have edited the answer to give a clear Explanation as @javaBeginner pointed. But this is unnecessary as the question clearly states that the array was sorted using Arrays.sort but anyways a clearer explanation won't hurt.

Answer 2

In contrast to your explanation, your code does not keep i fixed while j is decremented. In fact, every time j is decremented, i is incremented.

To carry out your intent, you would require two while loops - an outside one what increments i and an inner one that decrements j from test.length down to i+1.

However, @BlackPanther's approach appears to deliver the desired result with less computation, so I'd prefer it to your approach.

Answer 3

my way of doing this needs more array accesses than @BlackPanther's solution, but I finally made it work as following:edited.

int[] test = new int[] {1, 2, 3, 3, 3, 3, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9, 9};
        int i = 0;
        int j = test.length - 1;
        int[] copySegment;

        while (i < test.length)
        {
            while (j > i)
            {
                if (test[j] == test[i])
                {
                    for (int k = i; k <= j; k++)
                        System.out.print(test[k] + " ");
                    System.out.print("\n");
                    i = j + 1;
                    j = test.length;
                }
                j--;
            }
            i++;
            j = test.length - 1;
        }

Answer 4

Considering that the array is Pre-sorted, (otherwise, I can still do an Array.sort() to have them sorted) I came up with an easier method to do what you're doing..

int[] array = new int[] {1, 2, 3, 3, 3, 3, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9, 9};

Map<Integer, Integer> intList= new HashMap<Integer, Integer>(); 

int curCount=1;
for (int i=0; i<array.length-1; i++){
    if (array[i]==array[i+1] ){
        curCount++;
        if(i==array.length-2)
            intList.put(array[i], curCount);
    }
    else{
        intList.put(array[i], curCount);
        curCount=1;
    }

}

for (Map.Entry<Integer, Integer> entry : intList.entrySet())
{
    if(entry.getValue()<2)
        continue;
    else {
        for (int i=0; i<entry.getValue(); i++)
        System.out.println(entry.getKey());

    }
}

I have ran and tested this piece of code. Hope it helps.