1.intro
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
The above image can be looked as a top-level view of a staircase where you are at the base of the staircase. Each element can be uniquely identified by their index in the array (in a similar way as you could identify your friends by the step on which they were on in the above example).
2.array rotation
Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.
Rotation of the above array by 2 will make array
METHOD 1 (Using temp array)
Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store d elements in a temp array
temp[] = [1, 2]
2) Shift rest of the arr[]
arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
arr[] = [3, 4, 5, 6, 7, 1, 2]
Time complexity : O(n)
Auxiliary Space : O(d)
METHOD 2 (Rotate one by one)
leftRotate(arr[], d, n)
start
For i = 0 to i < d
Left rotate all elements of arr[] by one
end
To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]
Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Rotate arr[] by one 2 times
We get [2, 3, 4, 5, 6, 7, 1] after first rotation and [ 3, 4, 5, 6, 7, 1, 2] after second rotation.
Below is the implementation of the above approach :
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to rotate an array by // d elements
class RotateArray { /Function to left rotate arr[] of size n by d/
void leftRotate(int arr[], int d, int n)
{ for (int i = 0; i < d; i++)
leftRotatebyOne(arr, n);
} void leftRotatebyOne(int arr[], int n)
{ int i, temp;
temp = arr[0]; for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
} /* utility function to print an array */
void printArray(int arr[], int n)
{ for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
} // Driver program to test above functions
public static void main(String[] args)
{
RotateArray rotate = new RotateArray(); int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
rotate.leftRotate(arr, 2, 7);
rotate.printArray(arr, 7);
}
} </pre>
](javascript:void(0); "复制代码")
Time complexity : O(n * d)
Auxiliary Space : O(1)
METHOD 3 (A Juggling Algorithm)
This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
Here is an example for n =12 and d = 3. GCD is 3 and
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
a) Elements are first moved in first set – (See below
diagram for this movement)
</pre>
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;"> arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}
b) Then in second set.
arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}
c) Finally in third set.
arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}
code:</pre>
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to rotate an array by // d elements
class RotateArray { /Function to left rotate arr[] of siz n by d/
void leftRotate(int arr[], int d, int n)
{ int i, j, k, temp; int g_c_d = gcd(d, n); for (i = 0; i < g_c_d; i++) { /* move i-th values of blocks / temp = arr[i];
j = i; while (true) {
k = j + d; if (k >= n)
k = k - n; if (k == i) break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
} /UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{ int i; for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
} /*Fuction to get gcd of a and b*/
int gcd(int a, int b)
{ if (b == 0) return a; else
return gcd(b, a % b);
} // Driver program to test above functions
public static void main(String[] args)
{
RotateArray rotate = new RotateArray(); int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
rotate.leftRotate(arr, 2, 7);
rotate.printArray(arr, 7);
}
} </pre>
[
](javascript:void(0); "复制代码")
3.array reverse
Recursive Way :
- Initialize start and end indexes as start = 0, end = n-1
- Swap arr[start] with arr[end]
- Recursively call reverse for rest of the array.
Below is the implementation of the above approach :
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Recursive Java Program to reverse an array
import java.io.; class ReverseArray { / Function to reverse arr[] from start to end/
static void rvereseArray(int arr[], int start, int end)
{ int temp; if (start >= end) return;
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
rvereseArray(arr, start+1, end-1);
} / Utility that prints out an array on a line /
static void printArray(int arr[], int size)
{ for (int i=0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
} /Driver function to check for above functions*/
public static void main (String[] args) { int arr[] = {1, 2, 3, 4, 5, 6};
printArray(arr, 6);
rvereseArray(arr, 0, 5);
System.out.println("Reversed array is ");
printArray(arr, 6);
}
} </pre>
](javascript:void(0); "复制代码")
**4.Shuffle **
Given an array, write a program to generate a random permutation of array elements. This question is also asked as “shuffle a deck of cards” or “randomize a given array”. Here shuffle means that every permutation of array element should equally likely.
Let the given array be arr[]. A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[]. Randomly select an element from temp[], copy the randomly selected element to arr[0] and remove the selected element from temp[]. Repeat the same process n times and keep copying elements to* arr[1], arr[2], … .* The time complexity of this solution will be O(n^2).
Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates random number in O(1) time.
The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.
Following is the detailed algorithm
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 downto 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]
</pre>
Following is implementation of this algorithm.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java Program to shuffle a given array
import java.util.Random; import java.util.Arrays; public class ShuffleRand
{ // A Function to generate a random permutation of arr[]
static void randomize( int arr[], int n)
{ // Creating a object for Random class
Random r = new Random(); // Start from the last element and swap one by one. We don't // need to run for the first element that's why i > 0
for (int i = n-1; i > 0; i--) { // Pick a random index from 0 to i
int j = r.nextInt(i+1); // Swap arr[i] with the element at random index
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} // Prints the random array
System.out.println(Arrays.toString(arr));
} // Driver Program to test above function
public static void main(String[] args)
{ int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; int n = arr.length;
randomize (arr, n);
}
} </pre>
](javascript:void(0); "复制代码")
5.K’th Smallest/Largest Element in Unsorted Array
****Using Min Heap – HeapSelect****
We can find k’th smallest element in time complexity better than O(N Log N). A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.
The following is C++ implementation of above method.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// A C++ program to find k'th smallest element using min heap
include<iostream> #include<climits> using namespace std; // Prototype of a utility function to swap two integers
void swap(int *x, int y); // A class for Min Heap
class MinHeap
{ int harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); //To minheapify subtree rooted with index i
int parent(int i) { return (i-1)/2; } int left(int i) { return (2i + 1); } int right(int i) { return (2i + 2); } int extractMin(); // extracts root (minimum) element
int getMin() { return harr[0]; } // Returns minimum
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2; while (i >= 0)
{
MinHeapify(i);
i--;
}
} // Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{ if (heap_size == 0) return INT_MAX; // Store the minimum vakue.
int root = harr[0]; // If there are more than 1 items, move the last item to root // and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--; return root;
} // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{ int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l] < harr[i])
smallest = l; if (r < heap_size && harr[r] < harr[smallest])
smallest = r; if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
} // A utility function to swap two elements
void swap(int *x, int *y)
{ int temp = *x; *x = *y; *y = temp;
} // Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{ // Build a heap of n elements: O(n) time
MinHeap mh(arr, n); // Do extract min (k-1) times
for (int i=0; i<k-1; i++)
mh.extractMin(); // Return root
return mh.getMin();
} // Driver program to test above methods
int main()
{ int arr[] = {12, 3, 5, 7, 19}; int n = sizeof(arr)/sizeof(arr[0]), k = 2;
cout << "K'th smallest element is " << kthSmallest(arr, n, k); return 0;
} </pre>
](javascript:void(0); "复制代码")
QuickSelect
This is an optimization over QuickSort ,if QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java code for kth smallest element in an array
import java.util.Arrays; import java.util.Collections; class GFG
{ // Standard partition process of QuickSort. // It considers the last element as pivot // and moves all smaller element to left of // it and greater elements to right
public static int partition(Integer [] arr, int l, int r)
{ int x = arr[r], i = l; for (int j = l; j <= r - 1; j++)
{ if (arr[j] <= x)
{ //Swapping arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
} //Swapping arr[i] and arr[r]
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp; return i;
} // This function returns k'th smallest element // in arr[l..r] using QuickSort based method. // ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
public static int kthSmallest(Integer[] arr, int l, int r, int k)
{ // If k is smaller than number of elements // in array
if (k > 0 && k <= r - l + 1)
{ // Partition the array around last // element and get position of pivot // element in sorted array
int pos = partition(arr, l, r); // If position is same as k
if (pos-l == k-1) return arr[pos]; // If position is more, recur for // left subarray
if (pos-l > k-1) return kthSmallest(arr, l, pos-1, k); // Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
} // If k is more than number of elements // in array
return Integer.MAX_VALUE;
} // Driver program to test above methods
public static void main(String[] args)
{
Integer arr[] = new Integer[]{12, 3, 5, 7, 4, 19, 26}; int k = 3;
System.out.print( "K'th smallest element is " + kthSmallest(arr, 0, arr.length - 1, k) );
}
} </pre>
[
](javascript:void(0); "复制代码")
6.Largest Sum Contiguous Subarray
Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Kadane’s Algorithm:
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
</pre>
Explanation:
Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;"> Lets take the example:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = max_ending_here = 0
for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
Set max_ending_here = 0 because max_ending_here < 0
for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
Set max_ending_here = 0 because max_ending_here < 0
for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_so_far is updated to 4 because max_ending_here greater
than max_so_far which was 0 till now
for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3
for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1
for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2
for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
max_so_far is updated to 7 because max_ending_here is
greater than max_so_far
for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4
</pre>
Program:
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">import java.io.; // Java program to print largest contiguous array sum
import java.util.; class Kadane
{ public static void main (String[] args)
{ int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum contiguous sum is " + maxSubArraySum(a));
} static int maxSubArraySum(int a[])
{ int size = a.length; int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here)
max_so_far = max_ending_here; if (max_ending_here < 0)
max_ending_here = 0;
} return max_so_far;
}
} </pre>
](javascript:void(0); "复制代码")
**Algorithmic Paradigm: **Dynamic Programming
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to print largest contiguous // array sum
import java.io.; class GFG { static int maxSubArraySum(int a[], int size)
{ int max_so_far = a[0]; int curr_max = a[0]; for (int i = 1; i < size; i++)
{
curr_max = Math.max(a[i], curr_max+a[i]);
max_so_far = Math.max(max_so_far, curr_max);
} return max_so_far;
} / Driver program to test maxSubArraySum */
public static void main(String[] args)
{ int a[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = a.length; int max_sum = maxSubArraySum(a, n);
System.out.println("Maximum contiguous sum is "
+ max_sum);
}
} </pre>
[
1.intro
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
The above image can be looked as a top-level view of a staircase where you are at the base of the staircase. Each element can be uniquely identified by their index in the array (in a similar way as you could identify your friends by the step on which they were on in the above example).
2.array rotation
Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.
Rotation of the above array by 2 will make array
METHOD 1 (Using temp array)
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
- Store d elements in a temp array
temp[] = [1, 2] 2) Shift rest of the arr[]
arr[] = [3, 4, 5, 6, 7, 6, 7] 3) Store back the d elements
arr[] = [3, 4, 5, 6, 7, 1, 2]</pre>
](javascript:void(0); "复制代码")
Time complexity : O(n)
**Auxiliary Space : **O(d)
METHOD 2 (Rotate one by one)
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">leftRotate(arr[], d, n)
start
For i = 0 to i < d
Left rotate all elements of arr[] by one
end</pre>
](javascript:void(0); "复制代码")
To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]
Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Rotate arr[] by one 2 times
We get [2, 3, 4, 5, 6, 7, 1] after first rotation and [ 3, 4, 5, 6, 7, 1, 2] after second rotation.
Below is the implementation of the above approach :
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to rotate an array by // d elements
class RotateArray { /Function to left rotate arr[] of size n by d/
void leftRotate(int arr[], int d, int n)
{ for (int i = 0; i < d; i++)
leftRotatebyOne(arr, n);
} void leftRotatebyOne(int arr[], int n)
{ int i, temp;
temp = arr[0]; for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
} /* utility function to print an array */
void printArray(int arr[], int n)
{ for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
} // Driver program to test above functions
public static void main(String[] args)
{
RotateArray rotate = new RotateArray(); int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
rotate.leftRotate(arr, 2, 7);
rotate.printArray(arr, 7);
}
} </pre>
](javascript:void(0); "复制代码")
Time complexity : O(n * d)
Auxiliary Space : O(1)
METHOD 3 (A Juggling Algorithm)
This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
Here is an example for n =12 and d = 3. GCD is 3 and
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
a) Elements are first moved in first set – (See below
diagram for this movement)
</pre>
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;"> arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}
b) Then in second set.
arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}
c) Finally in third set.
arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}
code:</pre>
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to rotate an array by // d elements
class RotateArray { /Function to left rotate arr[] of siz n by d/
void leftRotate(int arr[], int d, int n)
{ int i, j, k, temp; int g_c_d = gcd(d, n); for (i = 0; i < g_c_d; i++) { /* move i-th values of blocks / temp = arr[i];
j = i; while (true) {
k = j + d; if (k >= n)
k = k - n; if (k == i) break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
} /UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{ int i; for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
} /*Fuction to get gcd of a and b*/
int gcd(int a, int b)
{ if (b == 0) return a; else
return gcd(b, a % b);
} // Driver program to test above functions
public static void main(String[] args)
{
RotateArray rotate = new RotateArray(); int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
rotate.leftRotate(arr, 2, 7);
rotate.printArray(arr, 7);
}
} </pre>
[
](javascript:void(0); "复制代码")
3.array reverse
Recursive Way :
- Initialize start and end indexes as start = 0, end = n-1
- Swap arr[start] with arr[end]
- Recursively call reverse for rest of the array.
Below is the implementation of the above approach :
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Recursive Java Program to reverse an array
import java.io.; class ReverseArray { / Function to reverse arr[] from start to end/
static void rvereseArray(int arr[], int start, int end)
{ int temp; if (start >= end) return;
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
rvereseArray(arr, start+1, end-1);
} / Utility that prints out an array on a line /
static void printArray(int arr[], int size)
{ for (int i=0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
} /Driver function to check for above functions*/
public static void main (String[] args) { int arr[] = {1, 2, 3, 4, 5, 6};
printArray(arr, 6);
rvereseArray(arr, 0, 5);
System.out.println("Reversed array is ");
printArray(arr, 6);
}
} </pre>
](javascript:void(0); "复制代码")
**4.Shuffle **
Given an array, write a program to generate a random permutation of array elements. This question is also asked as “shuffle a deck of cards” or “randomize a given array”. Here shuffle means that every permutation of array element should equally likely.
Let the given array be arr[]. A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[]. Randomly select an element from temp[], copy the randomly selected element to arr[0] and remove the selected element from temp[]. Repeat the same process n times and keep copying elements to* arr[1], arr[2], … .* The time complexity of this solution will be O(n^2).
Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates random number in O(1) time.
The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.
Following is the detailed algorithm
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 downto 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]
</pre>
Following is implementation of this algorithm.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java Program to shuffle a given array
import java.util.Random; import java.util.Arrays; public class ShuffleRand
{ // A Function to generate a random permutation of arr[]
static void randomize( int arr[], int n)
{ // Creating a object for Random class
Random r = new Random(); // Start from the last element and swap one by one. We don't // need to run for the first element that's why i > 0
for (int i = n-1; i > 0; i--) { // Pick a random index from 0 to i
int j = r.nextInt(i+1); // Swap arr[i] with the element at random index
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} // Prints the random array
System.out.println(Arrays.toString(arr));
} // Driver Program to test above function
public static void main(String[] args)
{ int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; int n = arr.length;
randomize (arr, n);
}
} </pre>
](javascript:void(0); "复制代码")
5.K’th Smallest/Largest Element in Unsorted Array
****Using Min Heap – HeapSelect****
We can find k’th smallest element in time complexity better than O(N Log N). A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.
The following is C++ implementation of above method.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// A C++ program to find k'th smallest element using min heap
include<iostream> #include<climits> using namespace std; // Prototype of a utility function to swap two integers
void swap(int *x, int y); // A class for Min Heap
class MinHeap
{ int harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); //To minheapify subtree rooted with index i
int parent(int i) { return (i-1)/2; } int left(int i) { return (2i + 1); } int right(int i) { return (2i + 2); } int extractMin(); // extracts root (minimum) element
int getMin() { return harr[0]; } // Returns minimum
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2; while (i >= 0)
{
MinHeapify(i);
i--;
}
} // Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{ if (heap_size == 0) return INT_MAX; // Store the minimum vakue.
int root = harr[0]; // If there are more than 1 items, move the last item to root // and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--; return root;
} // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{ int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l] < harr[i])
smallest = l; if (r < heap_size && harr[r] < harr[smallest])
smallest = r; if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
} // A utility function to swap two elements
void swap(int *x, int *y)
{ int temp = *x; *x = *y; *y = temp;
} // Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{ // Build a heap of n elements: O(n) time
MinHeap mh(arr, n); // Do extract min (k-1) times
for (int i=0; i<k-1; i++)
mh.extractMin(); // Return root
return mh.getMin();
} // Driver program to test above methods
int main()
{ int arr[] = {12, 3, 5, 7, 19}; int n = sizeof(arr)/sizeof(arr[0]), k = 2;
cout << "K'th smallest element is " << kthSmallest(arr, n, k); return 0;
} </pre>
](javascript:void(0); "复制代码")
QuickSelect
This is an optimization over QuickSort ,if QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java code for kth smallest element in an array
import java.util.Arrays; import java.util.Collections; class GFG
{ // Standard partition process of QuickSort. // It considers the last element as pivot // and moves all smaller element to left of // it and greater elements to right
public static int partition(Integer [] arr, int l, int r)
{ int x = arr[r], i = l; for (int j = l; j <= r - 1; j++)
{ if (arr[j] <= x)
{ //Swapping arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
} //Swapping arr[i] and arr[r]
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp; return i;
} // This function returns k'th smallest element // in arr[l..r] using QuickSort based method. // ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
public static int kthSmallest(Integer[] arr, int l, int r, int k)
{ // If k is smaller than number of elements // in array
if (k > 0 && k <= r - l + 1)
{ // Partition the array around last // element and get position of pivot // element in sorted array
int pos = partition(arr, l, r); // If position is same as k
if (pos-l == k-1) return arr[pos]; // If position is more, recur for // left subarray
if (pos-l > k-1) return kthSmallest(arr, l, pos-1, k); // Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
} // If k is more than number of elements // in array
return Integer.MAX_VALUE;
} // Driver program to test above methods
public static void main(String[] args)
{
Integer arr[] = new Integer[]{12, 3, 5, 7, 4, 19, 26}; int k = 3;
System.out.print( "K'th smallest element is " + kthSmallest(arr, 0, arr.length - 1, k) );
}
} </pre>
[
](javascript:void(0); "复制代码")
6.Largest Sum Contiguous Subarray
Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Kadane’s Algorithm:
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
</pre>
Explanation:
Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; color: rgb(0, 0, 0); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;"> Lets take the example:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = max_ending_here = 0
for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
Set max_ending_here = 0 because max_ending_here < 0
for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
Set max_ending_here = 0 because max_ending_here < 0
for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_so_far is updated to 4 because max_ending_here greater
than max_so_far which was 0 till now
for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3
for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1
for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2
for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
max_so_far is updated to 7 because max_ending_here is
greater than max_so_far
for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4
</pre>
Program:
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">import java.io.; // Java program to print largest contiguous array sum
import java.util.; class Kadane
{ public static void main (String[] args)
{ int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum contiguous sum is " + maxSubArraySum(a));
} static int maxSubArraySum(int a[])
{ int size = a.length; int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here)
max_so_far = max_ending_here; if (max_ending_here < 0)
max_ending_here = 0;
} return max_so_far;
}
} </pre>
](javascript:void(0); "复制代码")
**Algorithmic Paradigm: **Dynamic Programming
[
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Consolas !important; font-size: 17px !important;">// Java program to print largest contiguous // array sum
import java.io.; class GFG { static int maxSubArraySum(int a[], int size)
{ int max_so_far = a[0]; int curr_max = a[0]; for (int i = 1; i < size; i++)
{
curr_max = Math.max(a[i], curr_max+a[i]);
max_so_far = Math.max(max_so_far, curr_max);
} return max_so_far;
} / Driver program to test maxSubArraySum */
public static void main(String[] args)
{ int a[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = a.length; int max_sum = maxSubArraySum(a, n);
System.out.println("Maximum contiguous sum is "
+ max_sum);
}
} </pre>
](javascript:void(0); "复制代码")
