krylloff
BAN USERThere are several approaches here.
1. Put values of array to Hash (HashSet for instance). Iterate through array and for current a[i] check if (a[i] - k) exists in Hash. It takes O(n) complexity, O(n) space.
2. Sort array. Iterate through array and for current a[i] find (a[i] - k) item using binary search.
It takes O(n log n) complexity without additional space.
So final chose depends on your requirements
Here the fisrt approach:
public class SubtractResult {
public static void main(String[] args) {
new SubtractResult().solve();
}
public void solve() {
Integer a[] = {3,6,10,13};
int k = 3;
printPairs(a, k);
}
public void printPairs(Integer[] a, int k) {
Set<Integer> set = new HashSet<Integer>(Arrays.asList(a));
for (Integer i : a) {
if (set.contains(i - k)) {
System.out.println(i + ", " + (i - k));
}
}
}
}
This solution takes O(1) space - BitSet and result StringBuilder:
public class RedundantCharacters {
public static void main(String[] args) {
new RedundantCharacters().solve();
}
public void solve() {
String s = "qwertyasdfghytrewq";
System.out.print(removeRedundant(s));
}
public String removeRedundant(String s) {
StringBuilder sb = new StringBuilder();
BitSet bitSet = new BitSet();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!bitSet.get(ch)) {
sb.append(ch);
}
bitSet.set(ch);
}
return sb.toString();
}
}
The idea is to store information about every student in Map, where key is Student ID. Value of this Map is a special structure where the best 5 results are in PriorityQueue, but other are in some simple collection (like list).
So when we need to add new item we check if PriorityQueue has 5 items. If it has less - just add new item, otherwise we peek top item which is the worse among best 5 and compare it with given. After that we put new item to list or to priority queue (and put in list top heap item)
So add operation takes O(log 5) == O(1) constant time
public class StudentTest {
public static void main(String[] args) {
new StudentTest().solve();
}
public void solve() {
StudentRecord sr1 = new StudentRecord("1", 10, new Date());
StudentRecord sr2 = new StudentRecord("1", 10, new Date());
StudentRecord sr3 = new StudentRecord("1", 10, new Date());
StudentRecord sr4 = new StudentRecord("1", 2, new Date());
StudentRecord sr5 = new StudentRecord("1", 10, new Date());
StudentRecord sr6 = new StudentRecord("1", 1, new Date());
StudentRecord sr7 = new StudentRecord("1", 10, new Date());
StudentRegister studentRegister = new StudentRegister();
studentRegister.add(sr1);
studentRegister.add(sr2);
studentRegister.add(sr3);
studentRegister.add(sr4);
studentRegister.add(sr5);
studentRegister.add(sr6);
studentRegister.add(sr7);
System.out.println(studentRegister.getFinalScore("1"));
}
public class StudentRecord implements Comparable<StudentRecord> {
String id;
int score;
Date date;
public StudentRecord(String id, int score, Date date) {
this.id = id;
this.score = score;
this.date = date;
}
@Override
public int compareTo(StudentRecord that) {
return this.score - that.score;
}
}
public class StudentRegister {
private Map<String, StudentScoresCollection> register = new HashMap<String, StudentScoresCollection>();
public void add(StudentRecord... studentRecords) {
for (StudentRecord studentRecord : studentRecords) {
add(studentRecord);
}
}
public void add(StudentRecord studentRecord) {
if (!register.containsKey(studentRecord.id)) {
register.put(studentRecord.id, new StudentScoresCollection());
}
register.get(studentRecord.id).put(studentRecord);
}
public double getFinalScore(String studentId) {
if (!register.containsKey(studentId)) {
return -1;
}
return register.get(studentId).getFinalScore();
}
}
public class StudentScoresCollection {
private static final int TEST_NUBMER = 5;
PriorityQueue<StudentRecord> bestScores = new PriorityQueue<StudentRecord>();
Collection<StudentRecord> otherScores = new ArrayList<StudentRecord>();
double bestSum = 0;
public void put(StudentRecord studentRecord) {
if (bestScores.size() < TEST_NUBMER) {
bestScores.offer(studentRecord);
bestSum += studentRecord.score;
} else {
if (bestScores.peek().compareTo(studentRecord) < 0) {
StudentRecord record = bestScores.poll();
otherScores.add(record);
bestSum -= record.score;
bestScores.offer(studentRecord);
bestSum += studentRecord.score;
} else {
otherScores.add(studentRecord);
}
}
}
public double getFinalScore() {
return bestSum / 5.0;
}
}
}
One more recursive:
public class MemberPayoutUtil {
public static double calculatePayout(Member member) {
double salesRecruits = 0;
if (member.getRecruitedMembers() == null) {
return member.getMonthlySales() * 0.1;
}
for (Member otherMember : member.getRecruitedMembers()) {
salesRecruits += getDirectSales(otherMember);
}
return (member.getMonthlySales() * 0.1) + (salesRecruits * 0.04);
}
private static double getDirectSales(Member member) {
double sales = member.getMonthlySales();
if (member.getRecruitedMembers() == null) {
return sales;
}
for (Member otherMember : member.getRecruitedMembers()) {
sales += getDirectSales(otherMember);
}
return sales;
}
Solution for main and incidental diagonals
public class Diagonals {
public static void main(String[] args) {
int[][] matrix = {{1,2,3}, {4,5,6}, {7,8,9}};
new Diagonals().printDiagonals(matrix);
}
public void printDiagonals(int[][] matrix) {
StringBuilder mainDiagonal = new StringBuilder();
StringBuilder incidentalDiagonal = new StringBuilder();
for (int i = 0; i < matrix.length; i++) {
if (matrix[i].length != matrix.length) {
System.out.print("Not square matrix");
return;
}
mainDiagonal.append(matrix[i][i]);
mainDiagonal.append(' ');
incidentalDiagonal.append(matrix[i][matrix.length - i - 1]);
incidentalDiagonal.append(' ');
}
System.out.println("main Diagonal: " + mainDiagonal);
System.out.println("incidental Diagonal: " + incidentalDiagonal);
}
}
I think it is possible to use greedy aproach here
public class FindNegate {
public static void main(String[] args) {
int a[] = {1,2,3};
System.out.println(new FindNegate().findNegate(a));
int b[] = {1,2,3,4};
System.out.println(new FindNegate().findNegate(b));
}
public Collection<Integer> findNegate(int[] array) {
// greedy approach
Arrays.sort(array);
long sum = 0;
for (int val : array) {
sum += val;
}
if (sum % 2 == 1) {
return Collections.emptyList();
}
sum /= 2;
List<Integer> answer = new ArrayList<Integer>();
for (int i = array.length - 1; i >=0; i--) {
if (sum - array[i] >= 0) {
answer.add(array[i] * -1);
sum -= array[i];
}
if (sum == 0) {
return answer;
}
}
if (sum != 0) {
answer.clear();
}
return answer;
}
}
This solution is O(n + m) complexity and O(n) memory.
You get only one occurrence of distinguishable item in result collection. If you need to find all items - change answer HashSet to List.
Does anybody know the linear solution without additional memory (or O(log n) memory)?
public class FindCommonElements {
public static void main(String[] args) {
int a[] = {1, 2, 3, 3, 4, 5};
int b[] = {3, 3, 4, 5, 5, 6, 7};
System.out.println(new FindCommonElements().findCommonItems(a, b));
}
public Collection<Integer> findCommonItems(int[] first, int[] second) {
Set<Integer> setFirst = new HashSet<Integer>();
for (Integer val : first) {
setFirst.add(val);
}
Set<Integer> answer = new HashSet<Integer>();
for (Integer val : second) {
if (setFirst.contains(val)) {
answer.add(val);
}
}
return answer;
}
}
O(n) complexity with O(n) additional memory
public class Pairs {
public static void main(String[] args) {
new Pairs().solve(new int[] {1, 5, 3, 4, 2}, 2);
}
public void solve(int[] a, int k) {
Set<Integer> set = new HashSet<Integer>();
for (Integer i : a) {
set.add(i);
}
long ans = 0;
for (Integer i : a) {
if (set.contains(i + k)) {
ans++;
}
if (set.contains(i - k)) {
ans++;
}
}
System.out.print(ans / 2);
}
}
Rep
Repnatetouche, Applications Developer at Alcatel Lucent
My name is NateTouche . I currently live in Seattle . One desire that has always been a constant since As a ...
The space compexity of this approach is O(A), Where A is capacity of alphabet for given string.
- krylloff January 14, 2014