Dizide maksimum farkı bulun

Herhangi bir sayı çiftinin farkını döndürmek için bir algoritma üzerinde çalışıyorum, çiftteki daha büyük tamsayı, daha küçük bir tamsayıdan daha yüksek bir dizinde (dizide) meydana gelir. /> güçlü.

Örnekler ...

Dizi: [2, 3, 10, 2, 4, 8, 1]

Çözüm: 10 - 2 = 8

Çıktı: 8


Dizi: [7, 9, 5, 6, 3, 2]

Çözüm: 9 - 7 = 2

Çıktı: 2


İşte elimde ne var ama bütün testler için işe yaramıyor ...

var a = [22, 2, 4, 5, 6, 444, 1, 666];

// declare variables
var minNumber = a[0],                  //initilize to first element
    maxNumber = a[0],                  //--- ^
    minNumberIndex = 0,                //min index
    maxNumberIndex = a.length - 1;     //max index

// loop through each element in array
for(i = 0; i < a.length; i++) {

   //find min
    if (a[i] < minNumber && i < maxNumberIndex) {
        minNumber = a[i];
        minNumberIndex = i;
    }

   //find max
    if (a[i] >= maxNumber && i > minNumberIndex) {
        maxNumber = a[i];
        maxNumberIndex = i;
    }
}

// return results
console.log("max: \t" + maxNumber);
console.log("min: \t" + minNumber + "index: " + minNumberIndex);
console.log(maxNumber - minNumber);  

Lütfen yardım et!

4
Test senaryoları/örnekler mantıklı değil ... Gereksinimleri anlamıyorum.
katma yazar sebnukem, kaynak
daha net bir şekilde söyler misiniz? Ayrıca bir çifti ne oluşturur? Eğer çift baştan iki-iki ise, sadece uzunlukları olacak mı? '
katma yazar Amit Joki, kaynak
8 bir çift değil, yarım çift ... ne istediğinizi kafa karıştırıcı, belki de en azından istenen çıktılara daha fazla örnek ekleyin ve çiftleri daha iyi açıklayın.
katma yazar dandavis, kaynak

9 cevap

let MaxDifference = arr => {
  let maxDiff = null;
  for(let x = 0; x < arr.length; x++){
    for(let y = x+1; y < arr.length; y++){
        if(arr[x] < arr[y] && maxDiff < (arr[y] - arr[x])){
            maxDiff = arr[y] - arr[x]
        }
    }
  }
  return maxDiff === null ? -1 : maxDiff;
}
2
katma

es6 sürümü:

var a = [2, 3, 10, 2, 4, 8, 1];
var min = a[0];
var max = a[a.length-1];
var init = [[0,min], [a.length -1,max]];



var r = a.reduce((
            res, e,i
        )=>{
    var [[mini, min ], [maxi ,max]] = res;
    var t = res;
    if(e=max && i>mini){
       t = [[mini, min ], [i ,e]];
    }
    return t;
}, init);
console.log(r[1][1]-r[0][1]);
1
katma

İki diziniz olabilir. Hadi onlara minlr ve maxrl diyelim.

minlr - Where minlr[i] stores the minimum value till index i when going from left to right in the original array.

maxrl - Where maxrl[i] stores the maximum value till index i when going from right to left in the original array.

Bu 2 diziye sahip olduğunuzda, dizileri yinelersiniz ve maxrl [i] ve minlr [i] arasındaki maksimum farkı bulursunuz.

Yukarıdaki örneklerde:

  1. minlr = {2,2,2,2,2,2,1};

    maxrl = {10,10,10,8,8,8,1};

    So the answer in this case would be 10 - 2 = 8.

  2. minlr = {7,7,5,5,3,2};

    maxrl = {9,9,6,6,3,2};

    So the answer in this case would be 9 - 7 = 2

1
katma

Bu tamam? dizideki her öğe için önceki öğelere bakar ve farkı iç 'diffs' dizisine ekler (geçerli öğe daha büyükse). Daha sonra diffs dizisinin içindeki en büyük değeri döndürdüm.

var findMaxDiff = function(arr){
    var diffs = [];
    for(var i = 1; i < arr.length; i++){
        for(var j = 0; j < i; j++){
            if(arr[i] > arr[j]){
                diffs.push(arr[i]-arr[j]);
            }
        }
    }
    return Math.max.apply( Math, diffs );
}
0
katma

gerçekte herhangi bir döngüye ihtiyaç duymazsınız, sadece sizin için ağır kaldırmak için Math.max (), Math.min() ve [] .indexOf() kullanın:

function findDiff(a){  
  var max=Math.max.apply(0, a),
    slot=a.lastIndexOf(max),
    min=Math.min.apply(0, a.slice(0, slot));
  if(a.length && !slot && !min-.153479 )return findDiff(a.slice(1));
  return max-min;
}

//ex: findDiff([7, 9, 5, 6, 3, 2]) == 2
//ex: findDiff([666, 555, 444 , 33, 22, 23]) == 1
//ex: findDiff([2, 3, 10, 2, 4, 8, 1]) == 8
0
katma
! Min-.153479 ?????? Ayrıca, bu dizi üzerinde birden çok kez yinelenir ve okunamaz durumdadır.
katma yazar shinzou, kaynak
@Hoyen: evet, Kyle çok açık değildi ve gemiyi terk etmiş gibi görünüyor. Bence farkı iade etme konusunda haklısın, asıl noktam ihtiyaç duyulmayan döngülerden ve kullanıcı-arazi karşılaştırmalarından kaçınmak için doğal yöntemler kullanmaktı ... yaptığımızdan farklı bir yaklaşımın var ve umarım cevabın OP'ye yardımcı olacağını umuyorum. eğer hala yaşıyorsa. takibini takdir ediyorum.
katma yazar dandavis, kaynak
@Hoyen: Asıl düşüncelerimi işe yarayan bir çözüm üzerinde kullanmak için düzenlendi.
katma yazar dandavis, kaynak
Bu dizi için başarısız olur: [666, 555, 444, 33, 22, 23]; O dönmeli 1
katma yazar Hoyen, kaynak
23-22 = 1. Tüm diziler için problemin çözülmesi gerekir, öyle ki iki eleman arasındaki maksimum farkı döndürür, öyle ki daha büyük eleman daha küçük sayılardan sonra görünür. Verdiğim örnekte, 23, 22'den büyük ve fark 1'dir. İşte sorunu açıklayan bir link: geeksforgeeks.org/maximum-difference-between-two-elements
katma yazar Hoyen, kaynak
Aşağı oyu geri almaya çalıştım, ancak cevabınızı düzeltmeden bana izin vermiyor. Bunu yaptığım için üzgünüm.
katma yazar Hoyen, kaynak

Dizi içinde dolaşmak ve özyinelemeyi şu şekilde kullanmak:

function maxDifference(a){  
 var maxDiff = a[1] - a[0];  
  for(var i = 2; imaxDiff ? diff : maxDiff;
  }  
  if(a.length>1){
      a.shift();    
      var diff = maxDifference(a);
      maxDiff = diff>maxDiff ? diff : maxDiff;
  }

  return maxDiff;
}
        var x = [2, 3, 10, 2, 4, 8, 1];
        maxDifference(x);//returns 8
        x = [7, 9, 5, 6, 3, 2];
    maxDifference(x)//returns 2
0
katma
orijinal diziyi yok etmemek için,() shift() işlevinden önce dilimlemek isteyebilirsiniz ... (belki a = a.slice() yukarı?)
katma yazar dandavis, kaynak

<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false"> <div class="snippet-code">

maxdiff = 0;
a =  [2, 3, 10, 2, 4, 8, 1]
for (i=a.length-1; i >= 0; i--) {
  for (j=i-1; j >= 0; j--) {
    if (a[i] < a[j] ) continue;
    if (a[i] -a[j] > maxdiff) maxdiff = a[i] -a[j]
  }
}
console.log(maxdiff || 'No difference found')
</div> </div>
0
katma

Doğrusal zaman ve sabit bellekte:

function maxDiff (nums) {
  var diff = 0, left = 0, right = 0, cur_right = 0, cur_left = 0;
  for (var i = 0; i < nums.length; i++) {
    if (nums[i] < nums[cur_left]) {
      cur_left = i;
      if (cur_left > cur_right) {
        cur_right = cur_left;
      }
    }
    if (nums[i] >= nums[cur_right]) {
      cur_right = i;
    }
    if (nums[cur_right] - nums[cur_left] > diff) {
      diff = nums[cur_right] - nums[cur_left];
      right = cur_right;
      left = cur_left;
    }
  }
  return [diff, left, right];
}

Yalnızca farkın ne olduğuyla ilgileniyorsanız ve sayıların nerede gerçekleştiğiyle ilgilenmiyorsanız, left ve right öğelerine ihtiyacınız yoktur.

0
katma
özyinelemeli olmayan iki geçişli fikri ile oynuyordum, ama bu onları bir araya getiriyor. çok hoş! severim.
katma yazar dandavis, kaynak
var maxDiff = function() {
  var list = Array.prototype.slice.call(arguments, 0)[0];
  var start = new Date().getTime();
  if((list !== null) && (toString.call(list) !== "[object Array]")) {
    console.warn("not an array");
    return;
  }
  var maxDiff = list[1] - list[0];
  var min_element = list[0];
  var i, j;
  for(i = 1; i < list.length; i++) {
    if(list[i] - min_element > maxDiff) {
      maxDiff = list[i] - min_element;
    }
    if(list[i] < min_element) {
      min_element = list[i];
    }
  }
  var end = new Date().getTime();
  var duration = end - start;
  console.log("time taken:: " + duration + "ms");
  return maxDiff;
};
0
katma