kiran007
BAN USERprivate static void MaximumDiff()
{
int[] arr = { 7, 6, 15, 4, 3, 21, 1 };
int min = arr[0];
int max = arr[1];
int diff = max - min;
bool minchanged = false;
bool maxchanged = false;
for (int i = 1; i < arr.Length - 1; i++)
{
minchanged = false;
maxchanged = false;
if (arr[i] < min)
{
min = arr[i];
minchanged = true;
}
if (arr[i + 1] > max)
{
max = arr[i + 1];
maxchanged = true;
}
if (minchanged && maxchanged && (max - min) > diff)
diff = max - min;
if (maxchanged && (max - min) > diff)
diff = max - min;
}
Console.WriteLine(diff);
}
void findmixmax(int[] a)
{
int min = a[0];
int max = a[0];
for (int i = 1;i<a.length;i++)
{
if(a[i] < min)
{
min = a[i];
continue;
}
if(a[i] > max)
max = a[i];
}
cout<<"min"<<min<<endl;
cout<<"max"<<max<<endl;
}
Above code will do max of 3n/2 comparisons because of continue statement when a[i]<min. it will not check for max.
No of comparisions: 3n/2 max in worst case
Space complexity: O(1)
one Solution i think for this is:
1) Create a graph with [lat,long] as vertices and edges. Edge weight can be calculated as the distance between two vertices.
2) to find famous locations for a given [lat,long], take all edges whose weight is less than r (as given in question) and edge source/destination is a given[lat,long]
Time complexity will be O(N-1) where N = number of edges.
Pros: Search time will be less for any given [lat,long] as we stored the graph.
Cons: adding/removing new [lat,long] will take more time.
B+ tree is a data structure that can be used here.
- kiran007 May 28, 2015Leaf nodes contain (pointer to photograph stored in memory, time and favorite). and all leaf nodes are connected.
Now for inserting new record it will take O(logn base b) b - order of b+ tree
Search also it takes O(logn base b) Time complexity.