rob
BAN USERC++ solution. O( n logn ) time, the complexity of the sort. Also, O(n) space if all letters common.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
void CommonLetters(const char *str1, const char *str2){
int len1 = strlen(str1);
int len2 = strlen(str2);
std::vector<char> common;
bool chars[256];
memset(chars, 0, 256 * sizeof(bool));
int i;
char temp;
for(i = 0; i < len1; i++){
temp = tolower(str1[i]);
if( !chars[ temp ] )
chars[temp] = 1;
}
for(i = 0; i < len2; i++){
temp = tolower(str2[i]);
if( chars[temp] ) {
common.push_back( temp );
chars[temp] = 0; // avoid duplicates
}
}
std::sort( common.begin(), common.end());
std::vector<char>::iterator itr;
for(itr = common.begin(); itr != common.end(); itr++)
std::cout << *itr << std::endl;
}
My thoughts:
Firstly, pass inputs to test the merge:
1) empty lists
2) 1 empty / 1 nonempty
3) 2 non empty
Pass inputs to test finding the kth element:
1) size of merged list is less than k
2) size of merged list is greater than/equal to k
Also, will function notify programmer when lists of non numeric types passed to the function?
Compare outputs of functions to the programs specification. Do these inputs return the expected output? Eg, if lists are empty, should exception be thrown (b/c returning an int, such as a -1, could be confused as the kth to largest element)?
1) Insert 2nd array values into hash map
2) Iterate through 1st array and square each value
3) Check for squared value in hash map and print match
If you replace unordered_map ( find() runs O(n) time as worst case) with your own hash map and assume no collisions, this solution runs in O(n) time complexity.
void CheckSquares(int *a1, int *a2, int len1, int len2){
std::unordered_map<int, bool> ht;
int temp;
int i;
// 1) Insert 2nd array values into hash map
for(i = 0; i < len2; i++)
ht[ a2[i] ] = 1;
// 2) Iterate through 1st array, square the values and print matches
for(i = 0; i < len1; i++) {
temp = pow(a1[i], 2);
if( ht.find( temp ) != ht.end() )
std::cout << temp << std::endl;
}
}
1) Put matrix elements into array [O(n*m)]
2) Sort - i chose mergesort [O(n logn) for average case]
3) Select median element of sorted array [O(1)]
So time complexity is O(n*m).
Here's my code. There's probably a better solution because my code doesn't take advantage of the sorted rows.
double Get2dMatrixMedian(double **matrix, int n, int m){
int array_length = n*m;
double *array = new double[array_length];
double result;
int i, j;
// Put matrix elements into 1d array
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
array[j + i*m] = matrix[i][j];
// Sort the array
MergeSort(array);
// Select median element from sorted array
if( (n*m) % 2 == 0)
result = (array[ array_length/2 -1] + array[ array_length/2] )/2;
else
result = array[ array_length/2 ];
delete [] array;
return result;
}
too complicated?
#include <iostream>
using namespace std;
void RotateMatrix(char **matrix, int length){
int circles = length/2;
int i, j;
char temp;
for(i = 0; i < circles; i++) {
// Rotate Left
temp = matrix[i][i];
for(j = i; j < length - 1 - i; j++)
matrix[j][i] = matrix[j + 1][i];
// Rotate Bottom
for(j = i; j < length - 1 - i; j++)
matrix[length - 1 - i][j] = matrix[length - 1 - i][j+1];
// Rotate Right
for(j = length - 1 - i; j > i; j--)
matrix[j][length - 1 - i] = matrix[j - 1][length - 1 - i];
// Rotate Top
for(j = length - 1 - i; j > i; j--)
matrix[i][j] = matrix[i][j - 1];
matrix[i][i + 1] = temp;
}
}
void DisplayMatrix(char **matrix, int length){
int i, j;
for(i = 0; i < length; i++) {
for(j = 0; j < length; j++)
cout << matrix[i][j];
cout << endl;
}
cout << endl;
}
int main(){
int i;
int length;
char **matrix;
// 1) Get length
cout << "Enter length of square matrix: ";
cin >> length;
cout << endl;
// 2) Get matrix
matrix = new char*[length];
for(i = 0; i < length; i++)
matrix[i] = new char[length];
cout << "Enter the " << length << " is of the matrix: " << endl;
cin.ignore();
for(i = 0; i < length; i++) {
cin.getline(matrix[i], length + 1); // delim character will be extracted but discarded.
if(cin.gcount() < length) {
cout << "Need to enter " << length << " # characters." << endl;
i--;
}
else if( cin.fail() ){
cout << "Too many characters entered. " << endl;
cin.clear();
i--;
}
}
cout << endl;
// 3) Rotate Matrix
RotateMatrix(matrix, length);
// 4) Display Matrix
cout << "Rotated Matrix: " <<endl;
DisplayMatrix(matrix, length);
return 0;
}
I reduced my equation to 6n^2 - 12n + 8.
- rob September 29, 20156n^2 is number of sub cubes w/o accounting for overlapping sides and corners.
Subtract 12n, 12 is the number of sides and n is the length of each side. Each side is accounted for twice in 6n^2.
Subtract 8, the number of corners, which are accounted for 3 times in 6n^2.