tqjustc
BAN USERimport java.util.*;
public class id5639359996887040
{
public static void main(String[] args)
{
ArrayList<String> myList = new ArrayList<String>();
myList.add("abc"); myList.add("cab"); myList.add("dac");
myList.add("beed"); myList.add("deb"); myList.add("few");
myList.add("acd");
HashSet<String> mySet = new HashSet<String>();
for (int i = 0; i < myList.size(); i ++)
{
char[] charArr = myList.get(i).toCharArray();
Arrays.sort(charArr);
mySet.add(new String(charArr));
}
System.out.println("size: " + mySet.size());
}
}
import java.util.*;
public class find_popular_items
{
public static int find_freq(List<Integer> nums, int pos)
{
int freq1 = 0;
// binary search
if (pos < 0 || pos >= nums.size())
{
return 0;
}
int pivot = nums.get(pos);
int leftmost_pos = 0;
int rightmost_pos = nums.size()-1;
if (nums.get(leftmost_pos) != pivot)
{
int right1 = pos;
int left1 = leftmost_pos;
while(true)
{
int mid1 = (int) (right1 + left1)/2;
if (mid1 == left1 || mid1 == right1)
{
if (nums.get(left1) == pivot)
{
leftmost_pos = left1;
}
else
{
leftmost_pos = right1;
}
break;
}
else if(nums.get(mid1) == pivot && nums.get(mid1-1) != pivot)
{
leftmost_pos = mid1; break;
}
else if (nums.get(mid1) != pivot && nums.get(mid1+1) == pivot)
{
leftmost_pos = mid1 + 1; break;
}
else
{
if (nums.get(mid1) < pivot)
left1 = mid1;
else
right1 = mid1;
}
}
}
if (nums.get(rightmost_pos) != pivot)
{
int left1 = pos;
int right1 = rightmost_pos;
while(true)
{
int mid1 = (int) (right1 + left1)/2;
if (mid1 == left1 || mid1 == right1)
{
if (nums.get(right1) == pivot)
{
rightmost_pos = right1;
}
else
{
rightmost_pos = left1;
}
break;
}
else if(nums.get(mid1) == pivot && nums.get(mid1+1) != pivot)
{
rightmost_pos = mid1; break;
}
else if (nums.get(mid1) != pivot && nums.get(mid1-1) == pivot)
{
rightmost_pos = mid1 - 1; break;
}
else
{
if (nums.get(mid1) > pivot)
right1 = mid1;
else
left1 = mid1;
}
}
}
return (rightmost_pos - leftmost_pos + 1);
}
public static void find_func(List<Integer> nums, List<Integer> p_items)
{
// we only need to check freq of four items: n/4, n/2, 3n/4, n
// n/4
int list_size = nums.size();
int freq1 = find_freq(nums, (list_size/4));
int freq2 = find_freq(nums, (list_size/4*2));
int freq3 = find_freq(nums, (list_size/4*3));
int freq4 = find_freq(nums, (list_size));
if ((double)freq1 >= list_size/4.0)
p_items.add(nums.get(list_size/4));
if ((double)freq2 >= list_size/4.0)
p_items.add(nums.get(list_size/4*2));
if ((double)freq3 >= list_size/4.0)
p_items.add(nums.get(list_size/4*3));
if ((double)freq4 >= list_size/4.0)
p_items.add(nums.get(list_size-1));
}
public static void main(String[] args)
{
List<Integer> nums = new ArrayList<Integer>();
nums.add(1); nums.add(2); nums.add(3); nums.add(4);
nums.add(4); nums.add(4); nums.add(4); nums.add(4);
nums.add(5); nums.add(6); nums.add(7); nums.add(8);
List<Integer> p_items = new ArrayList<Integer>();
find_func(nums, p_items);
Hashtable<Integer,Integer> hs1 = new Hashtable<Integer,Integer>();
for (int i = 0; i < p_items.size(); i++)
{
if (hs1.containsKey(p_items.get(i)))
continue;
else
hs1.put(p_items.get(i), 0);
}
Enumeration<Integer> keys1 = hs1.keys();
List<Integer> new_p_items = new ArrayList<Integer>();
while( keys1.hasMoreElements())
new_p_items.add(keys1.nextElement());
System.out.println("size: "+new_p_items.size());
for (int i = 0; i < new_p_items.size(); i++)
{
System.out.println(new_p_items.get(i));
}
System.out.println("Program Ends.");
}
}
We can solve it using Greedy Algorithm.
- tqjustc April 10, 2017