Algorithm for finding a range of data in an array
3 answers
The pseudocode would be something like this:
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
int left = i;
while(i + 1 < array.length && array[i + 1] == 0) {
i++;
}
// print range [left, i]
}
}
Time complexity O(n)
, where n
is the length of the array. The complexity of space is constant.
+1
source to share
Let me write a multi-threaded approach in pseudocode form:
Function ZeroHunter()
Split the array into N segments (where N is multiple of number of threads available)
Create a Dictionary<SegmentNumber, Result>. Let call it DicResults.
For i = 0 to Number of segments
Result = ProcessSegmentOnNewThread(S)
DicResults.Add(i, Result)
Next
Wait for all threads to complete
ConcatResults(DicResults)
End Function
Code for ProcessSegmentOnNewThread:
Function ProcessSegmentOnNewThread(Segment S)
Create a new thread
List<int, int> lst;
while i < S.Length
if S[i] == 0 Then
NewEntry = lst.Add(i, i)
while i < S.Length and S[i] == 0
NewEntry.End++;
i++
end while
end if
i++
end while
Return the results in the form of List<int, int>
End Function
Code for ConcatResults ():
Function ConcatResults(DicResults)
Sort the input dictionary on segment number (the dictionary key that is)
For i = 0 to DicResults.Count - 1
If DicResult[i].End = DicResult[i+1].Start - 1
Set DicResult[i].End = DicResult[i+1].End
Remove DicResult[i+1] from the dictionary
End If
Next
Return DicResult
End Function
It should be noted that while this algorithm will beat non-streaming algorithms for very large arrays, you shouldn't use it for smaller arrays because the overhead of creating streams and combining the results will outweigh the potential benefit of streaming.
0
source to share
try this buddy ... !! hope it works well: D
#include <stdio.h>
int main()
{
int a[12] = {0,0,0,0,1,1,1,1,0,0,0,0};
int i;
int t = 0;
for( i = 0; i < (int)( sizeof(a) / sizeof(a[0])); i++) {
if(a[i] == t) {
int k = i;
while(i + 1 < (int)( sizeof(a) / sizeof(a[0])) && a[i + 1] == 0) {
i++;
}
printf("range(%d,%d)\n",k,i);
}
}
}
0
source to share