1). For example in the array 9,6,2,14,5,7,4 – 2 is a local minima as it is smaller than its left and right number 6 and 14. Similarly 5 is another local minima as it is between 14 and 7, both larger than 5. You need to find any one of the local minima.
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {1,5,17,15,12,10,7,11,6,2,4};
int min = localMin(arr , 0 , arr.length -1);
System.out.println("Min " + min);
}
public static int localMin(int[] arr , int start , int end) {
if (arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
if (arr[0] < arr[1]) {
return arr[0];
} else {
return arr[1];
}
}
int mid = (start + end) / 2;
if (arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1]) {
return arr[mid];
} if (arr[mid-1] < arr[mid]) {
return localMin(arr ,start , mid-1);
} else {
return localMin(arr,mid+1,end);
}
}
}
Missing Number in An Array
2). You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 .
Since numbers from 0 to n – 1 are sorted in an array, the first numbers should be same as their indexes. That’s to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(log n) time based on the binary search algorithm as implemented below:
/* package whatever; // don't place packageg name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {0, 1,2,4,5,6,7 , 8,9,10,11,12,13,14,15,16,17,18};
int number = missingNumber(arr , 0 , arr.length -1);
System.out.println("Missing " + number);
}
public static int missingNumber(int[] a , int start , int end) {
int mid = (start + end) /2;
if (a[mid] != mid && a[mid-1] == (mid -1)) {
return mid ;
}
if (a[mid-1] == (mid -1)) {
return missingNumber(a, mid+1 , end);
} else {
return missingNumber(a ,start , mid-1);
}
}
}
Find the Minimum Element in the Rotated Sorted array
3). Find the minimum element in the rotated sorted array.
For example we have array as 1,3,6,9,12,15.
Now suppose the array is rotated k times ( we don’t know k), such that array becomes
12,15,1,3,6,9
/* package whatever; // don't place packageg name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {6,9,12,15,1,3};
int elem = minElement(arr , 0 , arr.length-1);
System.out.println("Minimum " + elem);
}
public static int minElement(int[] a , int start , int end) {
int mid = (start + end) /2 ;
if (start == mid) {
return a[mid + 1];
}
if (a[start] > a[mid]) {
return minElement(a,start,mid-1);
}
else {
return minElement(a,mid+1,end);
}
}
}
Find a Peak Element in Array
4). A peak element in an integer array is defined as an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [2, 4, 8, 3], 8 is a peak element and your function should return the index number 2.
/* package whatever; // don't place packageg name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {1,5,9,11,13,2,6,3,14};
int peak = peakElement(arr , 0 , arr.length -1);
System.out.println("Peak " + peak);
}
public static int peakElement(int[] arr , int start , int end) {
if (arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
if (arr[0] > arr[1]) {
return arr[0];
} else {
return arr[1];
}
}
int mid = (start + end) / 2;
if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
return arr[mid];
} if (arr[mid-1] > arr[mid]) {
return peakElement(arr ,start , mid-1);
} else {
return peakElement(arr,mid+1,end);
}
}
}
No comments:
Post a Comment