Java code as well as the runtime and space requirements using Big O /* return th
ID: 3873459 • Letter: J
Question
Java code as well as the runtime and space requirements using Big O
/* return the number of times value appears in the sorted input array. Brute force. */ static int countOccurrences(intl values, value) t) , return the number of times value appears in the sorted input array. static int countOccurrences(intl values, value) f) Given a node in a linked list that looks like this: public class Node t public int value; public Node next This function should return true if the provided value is in the linked list. */ static boolean contains(Node head, int value)(h /* This function should return true if all the values in the linked list are unique. Optimize for speed. */ static boolean checkUnique(Node head) hExplanation / Answer
1. static int countoccurances(int []values, int value)
{
int i,count = 0,n=values.length;
return count;
}
Time Complexiety using brute force O(n)
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. To reduce time complexiety we can use binary search algorith as the array is already sorted , Function definition is as follow also we need two extra function which are defined as below:-
int count(int values[], int value)
{
int i,n = values.length; // index of first occurrence ofvalue in values[0..n-1]
int j; // index of last occurrence of value in values[0..n-1]
/* get the index of first occurrence of value */
i = first(values, 0, n-1, value, n);
/* If value doesn't exist in values[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of value. Note that we
are only looking in the subarray after first occurrence */
j = last(values, i, n-1, value, n);
/* return count */
return j-i+1;
}
/* if value is present in values[] then returns the index of FIRST occurrence
of value in values[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
Time complexiety using binary search algorithm is O(logn).
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3.static boolean contains(Node head, int value)
{
Node temp = head;
while(temp.hasnext())
{
if(temp.next()==value)
{
return true;
}
}
return false;
}
Time complexiety is O(n).
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4.
boolean checkUnique(Node head)
{
while(temp.hasnext())
{ //if first and last index are not same there is more that one same element means list does not //contains all unique element and return false
if(indexOf(temp.next())!=lastIndexOf(temp.next()))
{
return false;
}
}
}
return true;
}
Time complexiety in O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.