Post date: Jul 09, 2013 12:8:48 AM
Problem
You given an array:
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9
Solution
Generate a maximum table
Let i = current index, len = the length of array
1. Find min in the range of (0, i);
2. Find max in the rante of (i, len - 1)
3. If current value > min && current value < max, print it and exit
4. Loop to next elements
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find a tuple in ascending order
Created Date : 09-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
void FindTuple(int* arr, int len)
{
if(arr == NULL){
cout << "Invalid array, reference to NULL" << endl;
return;
}
if(len < 3){
cout << "Array has less three elements" << endl;
return;
}
int minElem = min(arr[0], arr[1]);
int* maxElems = new int[len];
int maxElem = arr[len - 1];
maxElems[len - 1] = maxElem;
for(int i = len - 2; i >= 0; i--)
{
if(maxElem < arr[i]){
maxElem = arr[i];
}
maxElems[i] = maxElem;
}
for(int i = 1; i < len - 1; ++i){
if(minElem < arr[i] && maxElems[i] > arr[i]){
cout << "(" << minElem << ", ";
cout << arr[i] << ", " << maxElems[i];
cout << ") is found" << endl;
delete[] maxElems;
return;
}
if(minElem > arr[i]) minElem = arr[i];
}
delete[] maxElems;
cout << "Nothing is found" << endl;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
FindTuple(arr, len);
cout << "--------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {3, 2, 1, 6, 5, 4, 9, 8, 7 };
DoTest(arr, sizeof(arr)/sizeof(arr[0]));
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1 };
DoTest(arr1, sizeof(arr1)/sizeof(arr1[0]));
int arr2[] = {1};
DoTest(arr2, sizeof(arr2)/sizeof(arr2[0]));
int arr3[] = {3, 1};
DoTest(arr3, sizeof(arr3)/sizeof(arr3[0]));
int arr4[] = {3, 2, 1};
DoTest(arr4, sizeof(arr4)/sizeof(arr4[0]));
int arr5[] = {1, 2, 3};
DoTest(arr5, sizeof(arr5)/sizeof(arr5[0]));
int arr6[] = {2, 3, 1};
DoTest(arr6, sizeof(arr6)/sizeof(arr6[0]));
int arr7[] = {1, 2, 3, 4};
DoTest(arr7, sizeof(arr7)/sizeof(arr7[0]));
int arr8[] = {2, 3, 1, 5};
DoTest(arr8, sizeof(arr8)/sizeof(arr8[0]));
int arr9[] = {2, 3, 1, 0};
DoTest(arr9, sizeof(arr9)/sizeof(arr9[0]));
return 0;
}
Output
The array is
3 2 1 6 5 4 9 8 7
(1, 6, 9) is found
--------------------------------
The array is
9 8 7 6 5 4 3 2 1
Nothing is found
--------------------------------
The array is
1
Array has less three elements
--------------------------------
The array is
3 1
Array has less three elements
--------------------------------
The array is
3 2 1
Nothing is found
--------------------------------
The array is
1 2 3
(1, 2, 3) is found
--------------------------------
The array is
2 3 1
Nothing is found
--------------------------------
The array is
1 2 3 4
(1, 2, 4) is found
--------------------------------
The array is
2 3 1 5
(2, 3, 5) is found
--------------------------------
The array is
2 3 1 0
Nothing is found
--------------------------------
Press any key to continue . . .