2016-08-19
这个问题主要与之前做过题目的不同点就是这里需要的数据结构不再是Arraylist，而是集合，所以在这里我使用了一个hashSet作为此问题的数据结构保存插入数据，并从set中删除或提取数据。
总体来说，算法上没有什么难度，都是常见的插入，删除，提取问题。唯一遇到的问题在getrandom上。因为HashSet中没有get方法，不能直接提取元素，需要对Set进行遍历来完成。
最开始我使用的遍历方法是用迭代器Iterator，但是尝试很多方法发现迭代器类型怎么都不能复制给一个int类型数完成返回。最后查找到for循环遍历的方法解决问题。
代码如下：
private HashSet<Integer> set;
/** Initialize your data structure here. */
public RandomizedSet() {
set = new HashSet<Integer>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(set.contains(val))
return false;
else{
set.add(val);
return true;
}
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(set.contains(val)){
set.remove(val);
return true;
}
else{
return false;
}
}
/** Get a random element from the set. */
public int getRandom() {
int random = (int)(Math.random()*set.size());
int i = 0;
int result = 0;
for(Integer itg : set){ //for循环遍历HashSet
if(i == random){ //第random个数即为返回的随机数
result = itg;
}
i++;
}
return result;
}
这道题的难点在于数组并不是蛇形有序的，意思是当前行的最后一个元素并不一定会小于下一行的首元素，所以我们并不能直接定位第K小的元素。
最开始我想的很多，想设计出一种巧妙的算法解决这一问题，但是最终没有设计出来，使用了一种思路简单的处理方法。
先定义一个ArrayList，将矩阵中的数都储存进去，之后，用java自带的sort函数进行排序，最后，get到排好序的ArrayList的第k个元素即可。
代码如下：
public int kthSmallest(int[][] matrix, int k) {
int width = matrix[0].length;
int height = matrix.length;
ArrayList<Integer> List = new ArrayList<Integer>();
for(int i = 0 ;i < height;i++){
for(int j = 0;j < width;j++){
List.add(matrix[i][j]);
}
}
Collections.sort(List);
return List.get(k-1);
}
但是在这样处理之后，我又查找了一些关于这道题解答的博客，发现了如下解法。
新解法： 记录每行最小数位置，每次n个最小位置中的最小位置，使其加以，继续循环直到循环次数大于k
public static int kthSmallest(int[][] matrix, int k) {
int[] tem=new int[matrix.length];
int[] temIndex=new int[matrix.length];
int tar=0;
for(int i=0;i<k;i++){
for(int j=0;j<matrix.length;j++)
tem[j]=matrix[j][temIndex[j]];
int temm=findSmall(tem, 0, tem.length-1);
if(i==k-1){
tar=matrix[temm][temIndex[temm]];
}
if(temIndex[temm]==matrix.length-1){
matrix[temm][temIndex[temm]]=Integer.MAX_VALUE;
}else {
temIndex[temm]++;
}
}
return tar;
}
static int findSmall(int[] t,int start,int stop){
if(start==stop)
return start;
else {
int zuo=findSmall(t, start, (start+stop)/2);
int you=findSmall(t, (start+stop)/2+1, stop);
if(t[zuo]<t[you])
return zuo;
else {
return you;
}
}
}
我最开始使用的方法是深度搜索，然后回溯，先对数组排序，然后当和大于target时就直接返回，做一个简单的剪枝，但是设计完之后，发现超时，尝试很多办法都没有解决。
然后查找了一些资料发现这实际上可以看作一个动态规划背包问题。求出[1, target]之间每个位置有多少种排列方式, 这样将问题分化为子问题. 状态转移方程可以得到为:
dp[i] = sum(dp[i - nums[j]]), (i-nums[j] > 0);
回溯代码如下：
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
array = nums;
calNum(0,nums.length,target);
return num;
}
public void calNum(int sum,int length,int target){
for(int i = 0;i < length;i++){
sum += array[i];
if(sum == target){
num++;
sum -= array[i];
break;
}
else if(sum < target){
calNum(sum,length,target);
sum -= array[i];
}
}
}
动态规划代码设计如下：
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i-nums[j]];
}
}
}
return dp[target];
}