RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a list search and an unusual sort. (Note that this ends today.)

Task 1: Lucky Integer

You are given an array of integers, @ints.

Write a script to find the lucky integer if found otherwise return -1. If there are more than one then return the largest.

A lucky integer is an integer that has a frequency in the array equal to its value.

I got lazy with this. In Perl:

sub luckyinteger($a) {

Build a freqency count.

  my %c;
  map {$c{$_}++} @{$a};

Get descending-sorted lists of keys and values.

  my @c1 = reverse sort values %c;
  my @c2 = reverse sort keys %c;

For each value starting with the largest,

  foreach my $v1 (@c1) {

For each key starting with the largest,

    foreach my $v2 (@c2) {

If the key's lookup equals the value, and the key equals the value, this is the one we want.

      if ($c{$v2} == $v1 && $v1 == $v2) {
        return $v2;
      }
    }
  }
  return -1;
}

Would have been better, in retrospect, to pull out only those values where k == v and take the largest, but I didn't think of it. Never mind. Rust's counter crate is easiest:

use counter::Counter;

fn luckyinteger(a: Vec<usize>) -> i32 {
    let c = a.into_iter().collect::<Counter<_>>();
    for pair in c.most_common_tiebreaker(|&a, &b| b.cmp(&a)) {
        if pair.0 == pair.1 {
            return pair.0 as i32;
        }
    }
    -1
}

Task 2: Relative Sort

You are given two list of integers, @list1 and @list2. The elements in the @list2 are distinct and also in the @list1.

Write a script to sort the elements in the @list1 such that the relative order of items in @list1 is same as in the @list2. Elements that is missing in @list2 should be placed at the end of @list1 in ascending order.

I used a counter for this one too. Python:

from collections import defaultdict

def relativesort(list1, list2):

Build a frequency count of list1.

  c = defaultdict(lambda: 0)
  for n in list1:
    c[n] += 1

Set up the output list.

  out = []

Push into it a number of copies of the item in list2 equal to its count in list1. Remove that item from the counter. (Which is a reason to use a defaultdict, other than simplifying the counter code; if the item doesn't appear in list1, the counter value will be zero and nothing will be added.)

  for i in list2:
    out.extend([i] * c[i])
    del c[i]

What's left is the counts of items in list1 that weren't in list2. Sort them and do the same thing.

  d = sorted(c.keys())
  for i in d:
    out.extend([i] * c[i])
  return out

Full code on github.