s********x
发帖数: 914 | 1 我试着写了一下，没有测，有bug请告诉我
public static int minDiffBetweenTwoOrderedArrays(int[] a, int[] b) {
// validate(a, b);
if (a.length > b.length) {
return minDiffBetweenTwoOrderedArrays(b, a);
} // now a.length <= b.length
int minDiff = Integer.MAX_VALUE;
int low = 0, high = b.length - 1;
for (int i : a) {
if (minDiff == 0) {
return 0;
}
if (i < b[0]) {
// element in a is less than the first element in b
... 阅读全帖 |
|
c*****e
发帖数: 67 | 2 给定两个排序数组A和B，找到A与B中元素最小差值。
如A={0,3}, B={2,7,9}, 结果是1（A中的3和B中的2的差值）
想到一个O(nlogn)的解法：取A中的每一个值，在B中进行binary search。贴个Java代
码如下。不知道有没有更好的解法。
public int minDiff(int[] a, int[] b) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
int n = a[i];
int low = 0;
int high = b.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (b[mid] == n)
return 0;
... 阅读全帖 |
|
p****e
发帖数: 3548 | 3 没测试过，任意数量的list
bool listcompr(ListNode * a, ListNode * b){
if(a == NULL) return true;
if(b == NULL) return false;
return a->valval;
}
int MinDiff(vector &a){
sort(a.begin(), a.end(), listcompr);
int s = 0;
while(s
if(s >= a.size() - 1) return -1;
int mindiff = INT_MAX;
while(mindiff > 0){
if(a[s+1]->val - a[s]->val < mindiff)
mindiff = a[s+1]->val - a[s]->val;
a[s] = a[s]->next;
i... 阅读全帖 |
|
x********3
发帖数: 160 | 4 第二题我想是可以用greedy的。我基本的思路是首尾两项肯定是在选的elements中的。
初始化是选择的序列是0,1,2..k-2,n-1（从0开始计）。循环从倒数第二项开始决定他
应该所在的index的位置，直到正数第二项为止。中间的调整的过程有点复杂，可能可
以简化。下面是我随便写的代码。写得蛮差的，欢迎大家测试指正。
$k = 4;
$a = Array(1, 2, 5, 6, 11, 16, 17);
$records = Array();
for ($i = 1; $i < $k - 1; $i++)
{
$record = new Record($a[$i] - $a[$i - 1], $i);
$records[$i - 1] = $record;
}
$records[$k - 2] = new Record($a[count($a) - 1] - $a[$k - 2], count($a) - 1);
for ($last = $k - 2; $last > 0; $last--)
{
for ($i = $records[$la... 阅读全帖 |
|
c*******r
发帖数: 610 | 5 贴一个，大家看看对不对:
//do not deal with array with size less than 2
int findMinDiff(int A[], int n)
{
if (n <2)
{
return -1;
}
int minElem = A[0];
int minDiff = abs(A[1] -A[0]);
for (int i = 1; i < n; ++i)
{
if (abs(A[i] - minElem) < minDiff)
{
minDiff = abs(A[i] - minElem);
}
if (A[i] < minElem)
{
minElem = A[i];
}
}
return minDiff;
} |
|
t**r
发帖数: 3428 | 6 我的代码：
很糟糕，大数据过不去
应该可以用bitmap 优化一下 今天懒得弄了
package topcoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
//B[0] = 0
//B[i] = A[B[i-1]], for every i between 1 and N-1, inclusive.
/*
* Permutation Child array
{0, 1, 2} {0, 0, 0}
{0, 2, 1} {0, 0, 0}
{1, 0, 2} {0, 1, 0}
{1, 2, 0} {0, 1, 2}
{2, 0, 1} {0, 2, 1}
{2, 1, 0} {0, 2, 0}
* */
public... 阅读全帖 |
|
c***l
发帖数: 8 | 7 A DP algorithm based on the balance partition algorithm (can google find the
algorithm) for the first question.
大牛看看有什么问题.
#include
#include
#include
using namespace std;
extern int mindiff(int i, int A[]);
int main()
{
int A[5]={3, 5, 7, 11, 13};
int min;
min=mindiff(5,A);
cout<
}
int mindiff(int n, int A[])
{
int i, j;
int max=0;
int jmin;
int result;
double min;
double sum=0;
for(i=0;i<=n-1;i++) { sum+=A[... 阅读全帖 |
|
r**h
发帖数: 1288 | 8 我的想法是，先sort三个数组
然后每个数组从头开始比较三个数的差，然后每次将最小的那个元素的数组指针向后移
动一位。不知道有没有反例啊
run了一个代码看上去是正确的
def getMinDiffTriplet(a, b, c):
minDiff, ma, mb, mc = 9999, -1, -1, -1
pa, pb, pc = 0, 0, 0
while not (pa == len(a)-1 and pb == len(b)-1 and pc == len(c)-1):
na, nb, nc = a[pa], b[pb], c[pc]
curDiff = max(abs(na-nb), abs(na-nc), abs(nb-nc))
if curDiff < minDiff:
minDiff = curDiff
ma, mb, mc = na, nb, nc
if na<=nb and na<=nc:
if p... 阅读全帖 |
|
