Anybody use this DP method?


  • 1
    F
    public class Solution
     {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            int len1=nums1.length, len2=nums2.length;
            int[] step= new int[len1];
            List<int[]> res= new ArrayList<int[]>();
            
            //记录一下从nums1到nums2的步数
            for(int i=0; i<Math.min(k,len1*len2); i++)
            {
                int min=Integer.MAX_VALUE;
                for(int a=0; a<len1; a++)
                {
                    if(step[a]>=len2) continue;
                    min=Math.min(min, nums1[a]+nums2[step[a]]);
                }
                for(int a=0; a<len1; a++)
                {
                    if(step[a]>=len2) continue;
                    if(nums1[a]+nums2[step[a]]==min)
                    {
                        res.add(new int[]{nums1[a], nums2[step[a]]});
                        step[a]++;
                        break;
                    }
                }
            }
            return res;
        }
    }
    

  • 0

    @fjejopgrew Format your code properly next time using ``` for code block, thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.