Geek Answers Handbook

Detect all indices of invalid zeros in the input string (change the algorithm I have)

My requirements are as follows:

Input: one array of integers (the value will be only 0/1) and an integer z

Process: detecting all indexes of invalid zeros

Invalid zero is a zero belonging to run 0s whose length is greater than or equal to z

Output: ArrayList containing all invalid zeros indexes

Example:

input:  Data: 1,0,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1        
    ζ : 2

output: 2,3,4,17,18

==============================================>

I am using the following algorithm and want to know if there is a better way to do this?

Algorithm: verification (A [1 ... n], ζ)

Counter ⇐ 0
For i ⇐ 1 to n do
    if A[i] == 0 then 
        counter ⇐ counter +1
        if i == n and counter >= ζ then
            for j ⇐ (n-counter)   to n do
                R.add(j)
    else
        if counter >= ζ
            for j ⇐ (i-counter-1)   to (i-1) do
                R.add(j)
        counter ⇐ 0
return R

thank

+4
source share
5 answers

I got this O (n) algorithm, although it seems a bit long.

Algorithm: validate(A[1…n], ζ)
    j ⇐ 0

    // Store all indices of zeroes in Q
    for i ⇐ 1 to n do
    if A[i] == 0 then
        j ⇐ j + 1
        Q[j] ⇐ i

    Qsize ⇐ j

    // if number of zeroes in input is less than ζ, return empty set
    if Qsize < ζ then
        return R //R is an Empty ArrayList

    //if any zero is invalid, return every index in Q
    if ζ == 1 then
        for i ⇐ 1 to Qsize do
            R.add(Q[i])
        return R

    flag ⇐ false
    // one loop to indentify valid zeroes, change their indices to 0
    // only keep invalid zeroes indices in Q
    for i ⇐ Qsize to ζ do   

        if Q[ i – ζ +1] – (i - ζ +1) == Q[i] – i then
            flag ⇐ true
            i ⇐ i – ζ +1 // for-loop will do one more i ⇐ i -1

        else if flag == true and Q[i] - i <> Q[ i + 1 ] – (i + 1) then
            flag ⇐ false
            i ⇐ i  +1 // for-loop will do one more i ⇐ i -1

        else
            Q[i] ⇐ 0

    // Put invalid zeroes indices into R to return
    for i ⇐ 1 to Qsize do
        if Q[i] <> 0 then
            R.add(Q[i])

    return R
+5
source

. .

A[0....n - 1]
R[0...n-1]
count = 0
For i ⇐ 0 to n - 1 do
    if A[i] == 0 then 
         R[count++] == i
return R
+3

, , . , 0, reset , 1. .

counter ⇐ 0
For i ⇐ 1 to n do
    if A[i] == 0 then 
        counter ⇐ counter +1
        if counter >= ζ then
            R.add(i)
    else
        counter ⇐ 0
return R

OK. " ". , , , , .

- 1, .

, ,

counter ⇐ 0
For i ⇐ 1 to n do
    if A[i] == 0 then 
        counter ⇐ counter +1
        if i == n and counter >= ζ then
            for j ⇐ (n-counter+1) to n do
                R.add(j)
    else
        if counter >= ζ
            for j ⇐ (i-counter) to (i-1) do
                R.add(j)
        counter ⇐ 0
return R

, == 1, "n-1" "n" "i-2" "i-1" , , "n" "n" "i-1" "i-1" .

# 2

, . 1 0. A [i] 0 1, . , . , , , , .

I think that you have (one pass and data processing sequentially) about as good as it does. Remember the golden rule. Do not preempt optimization . Check what you have and see if that is enough.

+2
source

Here is a simple algorithm that does not require an internal loop.

Assuming indices are from 1 to n

initialize two array lists of integers arr_list1 and arr_list2.

validate(A[1…n], ζ)
{    
 initialize an integer count=0
  for( i=1 to n)
   if(arr[i]==0)
    {
      increment count by 1;
      add i to arr_list;
    }
   else
    {
       if(count>=ζ)
        {
         count=0;
         copy contents of arr_list1 into arr_list2
         clear all_list1
         continue;
        }
       else
         {count=0;clear the arr_list1}
    }
}

To display, display the elements arr_list2.

+1
source

Algorithm:

validate(A[1…n], ζ)
j ⇐ 0

// Store all indices of zeroes in Q
for i ⇐ 1 to n do
if A[i] == 0 then
    j ⇐ j + 1
    Q[j] ⇐ i

Qsize ⇐ j

// if number of zeroes in input is less than ζ, return empty set
if Qsize < ζ then
    return R //R is an Empty ArrayList

//if any zero is invalid, return every index in Q
if ζ == 1 then
    for i ⇐ 1 to Qsize do
        R.add(Q[i])
    return R

flag ⇐ false
// one loop to indentify valid zeroes, change their indices to 0
// only keep invalid zeroes indices in Q
for i ⇐ Qsize to ζ do   

    if Q[ i – ζ +1] – (i - ζ +1) == Q[i] – i then
        flag ⇐ true
        i ⇐ i – ζ +1 // for-loop will do one more i ⇐ i -1

    else if flag == true and Q[i] - i <> Q[ i + 1 ] – (i + 1) then
        flag ⇐ false
        i ⇐ i  +1 // for-loop will do one more i ⇐ i -1

    else
        Q[i] ⇐ 0

// Put invalid zeroes indices into R to return
for i ⇐ 1 to Qsize do
    if Q[i] <> 0 then
        R.add(Q[i])

return R
+1
source

More articles:


All Articles