Compact a given array problem
Dont know whether this is a duplicate, but this was an interview question asked to me. Given an array of random numbers and -1 placed inb开发者_Python百科etween, I have to compact the array meaning all the -1s are to be replaced and the final output should be the last valid index with the fresh array. For example.
Input:
3 4 -1 -1 -1 5 8 -1 8
Output:
3 4 5 8 8 5 8 -1 8 and last valid index is 4
Input:
-1 -1 -1 -1 -1 2
Output:
2 -1 -1 -1 -1 2 and last valid index is 0
Input:
-1 -1 -1 3 3 3
Output:
3 3 3 3 3 3 and last valid index is 2
You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.
int K=0
FOR i=0; i<LEN; i++
IF arr[i]!=-1
arr[K]=arr[i]
K++
END IF
RETURN K-1
Something like that ? it's PHP
<?php
$array = array('3','4','-1','-1','-1','5','8','-1','8');
$count = count($array);
$k = 0;
$i = 0;
while($i < $count && $k < $count)
{
echo $array[$i];
if($array[$i] == '-1')
{
echo '|';
if ($i>=$k){$k = $i + 1;}
$found = false;
while($k < $count && !$found)
{
echo 'X';
if($array[$k] != '-1')
{
$array[$i] = $array[$k];
$found = true;
}
$k++;
}
}
$i++;
}
print_r($array);
echo 'Last index'.($i - 1);
?>
import java.util.Arrays;
public class Compact {
static int previousValid(int[] nums, int startIndex) {
while (--startIndex >= 0 && nums[startIndex] == -1);
return startIndex;
}
static int nextInvalid(int[] nums, int startIndex) {
while (++startIndex < nums.length && nums[startIndex] != -1);
return startIndex;
}
static void compact(int... nums) {
int last = previousValid(nums, nums.length);
for (int h = -1, t = last + 1;
(h = nextInvalid(nums, h)) < (t = previousValid(nums, t));
) {
nums[last = h] = nums[t];
}
System.out.println(Arrays.toString(nums) + "; last valid = " + last);
}
public static void main(String[] args) {
compact(3, 4, -1, -1, -1, 5, 8, -1, 8);
// "[3, 4, 8, 8, 5, 5, 8, -1, 8]; last valid = 4"
compact(-1, -1, -1, -1, -1, 2);
// "[2, -1, -1, -1, -1, 2]; last valid = 0"
compact(-1, -1, -1, 3, 3, 3);
// "[3, 3, 3, 3, 3, 3]; last valid = 2"
compact(-1, -1, -1);
// "[-1, -1, -1]; last valid = -1"
compact(6, 6, 6);
// "[6, 6, 6]; last valid = 2"
}
}
Key ideas:
- Use
previousValid
andnextInvalid
helper methods to make logic clearer - Keep track of
h
andt
for "head" and "tail"h
findsnextInvalid
t
findspreviousValid
- Keep assigning
nums
from indext
toh
whileh < t
精彩评论