深切感受到了Java大法的妙……之后努力用java实现…
对键值对(hashmap)以值排序构建大小为k的小顶堆。使用java的优先队列实现
class Solution {
public int[] topKFrequent(int[] nums, int k)
{
Map<Integer,Integer>map=new HashMap<>();
for(int num:nums)//java的for遍历特性
{
map.put(num,map.getOrDefault(num,0)+1);//getOrDefalt函数的使用
}
PriorityQueue<int[]>sort=new PriorityQueue(new Comparator<int[]>()
{
public int compare(int[] a,int[] b)
{
return a[1]-b[1];//小顶堆的默认比较函数,值小的优先出队
}
});
for(Map.Entry<Integer,Integer>entry:map.entrySet())//用entrySet导出映射,用
{
int num=entry.getKey(),value=entry.getValue();
if(sort.size()==k)
{
if(sort.peek()[1]<value)
{
sort.poll();
sort.offer(new int[]{num,value});
}
}
else
{
sort.offer(new int[]{num,value});
}
}
int[] res=new int[k];
for(int i=0;i<k;i++)
{
res[i]=sort.poll()[0];
}
return res;
}
}
java二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root)
{
LinkedList<List<Integer>>ans=new LinkedList<>();
if(root==null)
return ans;
Queue<TreeNode>queue=new LinkedList<>();//用LinkedList类实现的队列
queue.add(root);
while(!queue.isEmpty())
{
List<Integer>oneline=new LinkedList<>();
int n=queue.size();//每层的节点数量
for(int i=0;i<n;i++)
{
TreeNode p=queue.poll();
oneline.add(p.val);
if(p.left!=null)
queue.add(p.left);
if(p.right!=null)
queue.add(p.right);
}
ans.add(oneline);
}
return ans;
}
}
二分搜索插入实现
class Solution {
int binsearch(int[] nums,int target,int left,int right)
{
if(left==right)
{
if(target==nums[left])
return left;
else if(target<nums[left])
return left;
else
return left+1;
}
int middle=(left+right)/2;
if(target==nums[middle])
{
return middle;
}
else if(target<nums[middle])
{
return binsearch(nums,target,left,middle);
}
else{
return binsearch(nums,target,middle+1,right);
}
}
public int searchInsert(int[] nums, int target)
{
return binsearch(nums,target,0,nums.length–1);
}
}