美文网首页
data structure of linked list

data structure of linked list

作者: 小水杯_c2ca | 来源:发表于2019-11-30 16:31 被阅读0次

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).


image

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.


Array

Rotation of the above array by 2 will make array

ArrayRotation1

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>

ArrayRotation

<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 :

  1. Initialize start and end indexes as start = 0, end = n-1
  2. Swap arr[start] with arr[end]
  3. 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.

shuffle-array

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-algorithm

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); "复制代码")
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).


image

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.


Array

Rotation of the above array by 2 will make array

ArrayRotation1

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

  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]</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>

ArrayRotation

<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 :

  1. Initialize start and end indexes as start = 0, end = n-1
  2. Swap arr[start] with arr[end]
  3. 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.

shuffle-array

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-algorithm

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); "复制代码")

相关文章

网友评论

      本文标题：data structure of linked list

      本文链接：https://www.haomeiwen.com/subject/vsbowctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|data structure of linked list|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！